Haskell中的Point Free问题

Question

我试图将以下haskell代码转换为点自由风格,但没有用.

bar f g xs = filter f (map g xs )

我是哈斯凯尔的新手,任何帮助都会很棒

Answer 1

转换为无点样式可以完全机械地完成,但是如果不熟悉Haskell语法的基本原理(如左关联函数应用程序并且与之x + y相同)则很难(+) x y.我假设您对Haskell语法感到满意; 如果没有,我建议首先浏览LYAH的前几章.

您需要以下组合器,它们位于标准库中.我还从组合子演算中给出了他们的标准名称.

id :: a -> a                                   -- I
const :: a -> b -> a                           -- K
(.) :: (b -> c) -> (a -> b) -> (a -> c)        -- B
flip :: (a -> b -> c) -> (b -> a -> c)         -- C
(<*>) :: (a -> b -> c) -> (a -> b) -> (a -> c) -- S

一次使用一个参数.将左侧的参数移动到右侧的lambdas,例如

f x y = Z

变

f = \x -> \y -> Z

我喜欢一次做一个这个论点,而不是一次性做,它看起来更干净.

然后根据以下规则消除刚刚创建的lambda.我将使用小写字母表示文字变量,大写字母表示更复杂的表达式.

1. 如果有\x -> x,请更换id
2. 如果你有\x -> A,在哪里没有出现A任何表达式x,请替换为const A
3. 如果你有\x -> A x,在哪里x没有发生A,替换为A.这被称为"eta收缩".
4. 如果你有\x -> A B,那么
   1. 如果x发生在这两个A和B,更换(\x -> A) <*> (\x -> B).
   2. 如果x发生在,只需A更换flip (\x -> A) B
   3. 如果x恰好发生B,替换为A . (\x -> B),
   4. 如果x在任一不发生A或B,还有,还有,我们应该已经使用其他规则.

然后向内工作,消除你创造的lambda.让我们使用这个例子:

f x y z = foo z (bar x y)
-- Move parameter to lambda:
f x y = \z -> foo z (bar x y)
-- Remember that application is left-associative, so this is the same as
f x y = \z -> (foo z) (bar x y)
-- z appears on the left and not on the right, use flip
f x y = flip (\z -> foo z) (bar x y)
-- Use rule (3) 
f x y = flip foo (bar x y)

-- Next parameter
f x = \y -> flip foo (bar x y)
-- Application is left-associative
f x = \y -> (flip foo) (bar x y)
-- y occurs on the right but not the left, use (.)
f x = flip foo . (\y -> bar x y)
-- Use rule 3
f x = flip foo . bar x

-- Next parameter
f = \x -> flip foo . bar x
-- We need to rewrite this operator into normal application style
f = \x -> (.) (flip foo) (bar x)
-- Application is left-associative
f = \x -> ((.) (flip foo)) (bar x)
-- x appears on the right but not the left, use (.)
f = ((.) (flip foo)) . (\x -> bar x)
-- use rule (3)
f = ((.) (flip foo)) . bar
-- Redundant parentheses
f = (.) (flip foo) . bar

你去,现在尝试你的!决定使用哪条规则并不是很聪明:使用适用的任何规则,您将取得进展.

Answer 2

这两个现有的答案并没有真正以一种阐明的方式回答你的具体问题:一个是"这里是规则,为自己解决",另一个是"这里是答案,没有关于规则如何生成的信息它."

前三个步骤非常简单,包括通过写入x从表单中删除一个共同点.基本上它是在说"如果你可以在表格中写下这个东西而你想要删除它,将所有的美元兑换成点,:h x = f (g x)h = f . ga $ b $ c $ ... $ y $ zza . b . c . ... . y

bar f g xs = filter f (map g xs)
           = filter f $ (map g xs)
           = filter f $ map g $ xs -- because a $ b $ c == a $ (b $ c).
bar f g    = filter f . map g
           = (filter f .) (map g)
           = (filter f .) $ map $ g
bar f      = (filter f .) . map

所以这最后f是唯一棘手的部分,而且它很棘手,因为f它不是表达式的"结束".但是看一下,我们看到这是一个(. map)应用于表达式其余部分的函数部分:

bar f = (.) (filter f) . map
bar f = (. map) $ (.) $ filter $ f
bar   = (. map) . (.) . filter

这就是当你没有复杂的东西f x x出现时,你如何减少表达式.一般来说,有一个flip f x y = f y x"翻转参数" 的功能; 你总是可以用它来移动f到另一边.flip (.) map . (.) . filter如果您包含显式翻转调用,我们将在此处.

Answer 3

我问过lambdabot,一个挂在各种Haskell IRC频道上的机器人,可以自动计算出无点的等价物.命令是@pl(毫无意义).

10:41 <frase> @pl bar f g xs = filter f (map g xs )
10:41 <lambdabot> bar = (. map) . (.) . filter

点免费版bar是:

bar = (. map) . (.) . filter

这可以说比原始(非点免费)代码更难以理解.在决定是否根据具体情况使用无点样式时,请使用您的良好判断.

最后,如果你不关心IRC,那么有基于网络的无点转换器,如Blunt(由@TaylorFausak提供),pointfree命令行程序和其他工具.