Haskell 点免费问题

Question

我正在尝试将以下 Haskell 代码转换为点自由样式，但无济于事。

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

我是 Haskell 的新手，任何帮助都将非常有用。

Answer 1

我问 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，可以使用基于网络的免费积分 pointfree.io, the pointfree 命令行程序和其他工具等转换器。

Answer 2

转换为 pointfree 风格可以完全机械地完成，尽管如果不熟悉 Haskell 语法的基本原理（如左关联函数应用程序和 x + y 与 [=15 相同）就很难=].我假设您对 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

一次使用一个参数。将左侧的参数移动到右侧的 lambda，例如

f x y = Z

变成

f = \x -> \y -> Z

我喜欢一次只做一个论点而不是一次全部，这样看起来更干净。

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

如果您有 \x -> x，请替换为 id
如果您有 \x -> A，其中 A 是 x 未出现的任何表达式，请替换为 const A
如果您有 \x -> A x，其中 x 未出现在 A 中，请替换为 A。这被称为 "eta contraction"。
如果你有\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 3

现有的两个答案都没有真正以阐明的方式回答您的具体问题：一个是 "here are the rules, work it out for yourself"，另一个是 "here is the answer, no information about how the rules generate it."

前三个步骤非常简单，包括通过编写 h = f . g 从 h x = f (g x) 形式的内容中删除常见的 x。本质上它是说“如果你可以用 a $ b $ c $ ... $ y $ z 的形式写东西并且你想删除 z，把所有的美元换成点，a . 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 不在表达式的 "end" 处。但是看一下，我们看到这是一个函数部分 (. map) 应用于表达式的其余部分：

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

这就是当你没有像 f x x 之类的复杂东西出现在其中时，你如何减少表达式。一般来说有一个函数flip f x y = f y x which "flips arguments";你总是可以用它把 f 移到另一边。如果您包括显式翻转调用，我们这里有 flip (.) map . (.) . filter。

Haskell 点免费问题

Point Free problems in Haskell

haskell

pointfree