一种简单啰嗦的强行point-free的方法
2016 年 8 月 10 日
最近做codewars上的Haskell的水题的时候（难题我也不会），基本上是尽量用一种point-free的风格(https://en.wikipedia.org/wiki/Tacit_programming)去写的。我个人理解也就是函数的实现不写出参数，只通过curry和组合等来实现，例如：
1 2 3 4 5 6 7 8 9 10 11 12 13 | -- let add a b = a + b let add = (+) -- let factorial n = product [1..n] let factorial = product . enumFromTo 1 -- let isPalindrome str = reverse str == str let isPalindrome = reverse >>= (==) -- 下面几个的point-free style作为练习 -- let k f x = f -- let g x y f = f x y -- let triple f x = f x x x |
另外这里也不认可出现用lambda形式代入参数如：
1 2 | let g = \x y f -> f x y --这也不是本文讨论的 |
这里用一个生成的方法来实现一个比较通用的方案，其实应该也可以用haskell的point-free风格代码来实现这套代码而不是生成，这里用Ruby生成。
注意到:
1 | let f x y = a (b x y) |
也可以写成
1 2 3 | let f x y = ((a.) . b) x y -- 即 let f = (a.) . b |
每次多一个参数就会是最里面多一个
1 2 | ... (a .) . ... ... ( ((a .) .) . (a .)) . ... |
等等的结构，也就是组合前面是一个(a .)的形式
另外，如果我们把tuple视为栈
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | > let f = (3, (2, 1)) > let push = (,) push 4 f -- (4, (3, (2, 1))) > let pop = snd pop f -- (2, 1) > let modify = first modify (+1) f -- (4, (2, 1)) > let apply = (uncurry ($) . (first *** id)) > let g = ((+1), (2, 3)) apply g -- (3, 3) 另外实现几个从forth拿过来的栈运算 >let vdup = modify (fst >>= (,)) 复制栈顶 (a, b) -> b vdup f -- (3, (3, (2, 1)) >let vswap = modify ((fst . snd) &&& (fst &&& (snd . snd))) 交换栈顶二个元素 (a, (b, c)) -> (b, (a, c)) vswap f -- (2, (3, 1)) >let vover = modify ((fst . snd) &&& id) over运算， 把栈顶的下一个元素复制一份压在顶上，(a, (b, c)) -> (b, (a, (b, c))) vover f -- (2, (3, (2, 1))) 等等可以把forth的栈操作都实现出来 |
于是这样就可以实现一组DSL(https://github.com/Artoria/pf-builder)了，比如海伦公式的实现
heron a b c = let s = (a + b + c) / 2 in s * (s – a) * (s – b) * (s – c)
下面的思路是通过build生成函数体
首先把三个参数a b c转成[c, b, a]
然后应用 (/2) . sum得到s
然后把s变成(s-), map到[c, b, a]上，变成[s-c, s-b, s-a], 然后对他它用product, 并且乘上这个积和s
就是结果
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | puts Builder.new{ push_arg modify "(: [])" push_arg push_const "(:)" apply apply push_arg push_const "(:)" apply apply modify_dup "(/2) . sum" vover vover modify "(-)" push_const "map" apply apply modify "product" push_const "(*)" apply apply modify "sqrt" }.finish! |
得到的结果,反正就是不能看了：
1 | ((((((((((((((((((((((((((( fst . (first (sqrt))) . (uncurry ($) . (first *** id))) . (uncurry ($) . (first *** id))) . ((,) ((*)))) . (first (product))) . (uncurry ($) . (first *** id))) . (uncurry ($) . (first *** id))) . ((,) (map))) . (first ((-)))) . ((fst . snd) &&& id)) . ((fst . snd) &&& id)) . (first ((/2) . sum))) . (fst >>= (,))) . (uncurry ($) . (first *** id))) . (uncurry ($) . (first *** id))) . ((,) ((:)))) .) . flip (,)) . (uncurry ($) . (first *** id))) . (uncurry ($) . (first *** id))) . ((,) ((:)))) .) . flip (,)) . (first ((: [])))) .) . flip (,)) undefined) |
另外，因为point-free的函数也是函数，可以嵌套
比如fib n = foldr (\_ (x, y) -> (y, x+y)) (1, 0) [1..n]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | puts Builder.new { push_arg modify "enumFromTo 1" push_const "(1, 0)" push_const Builder.new{ push_arg vpop push_arg modify "snd &&& (liftA2 (+) fst snd)" }.finish! push_const "foldr" apply apply apply modify "snd" }.finish! |
得到的结果
1 | ((((((((((( fst . (first (snd))) . (uncurry ($) . (first *** id))) . (uncurry ($) . (first *** id))) . (uncurry ($) . (first *** id))) . ((,) (foldr))) . ((,) (((((((( fst . (first (snd &&& (liftA2 (+) fst snd)))) .) . flip (,)) . snd) .) . flip (,)) undefined)))) . ((,) ((1, 0)))) . (first (enumFromTo 1))) .) . flip (,)) undefined) |