Haskell中的点自由问题

Question

Haskell中的点自由问题

13

我试图将以下Haskell代码转换为无点风格，但一直未能成功。

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

我是Haskell的新手，希望能得到任何帮助。

- Lee

6

请注意，在某些情况下（比如这个例子），无点风格版本可能比原来的代码更难读。除非你想要混淆代码，否则请谨慎使用无点风格。 - chi

3个回答

8

两个现有的答案并没有以一种清晰明了的方式回答你的具体问题：一个是“这是规则，请自己解决”；另一个是“这是答案，没有关于规则如何生成它的信息。”

前三步非常简单，包括从形如 h x = f (g x) 的某个东西中删除一个常见的 x，方法是编写 h = f . g。实际上，它是在说：“如果您可以将事物写成形式为 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不在表达式的“末尾”。但是仔细观察，我们可以看到这是应用于表达式其余部分的函数部分(. 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。

- CR Drost

6

我向在不同的Haskell IRC频道中活跃的机器人lambdabot询问自动计算无参等效项。命令是@pl（无意义）。

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

bar的无点版本如下：

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

这可能比原始代码（非point-free风格）更难理解。在逐案决定是否使用point-free风格时，请运用自己的判断力。

最后，如果你不喜欢IRC，还有基于Web的point-free转换工具，例如pointfree.io，pointfree 命令行程序以及其他工具。

- frasertweedale

4

如果您不想启动IRC客户端，我写了一个网站服务来为您进行转换。它叫做Blunt: https://blunt.herokuapp.com/#input=bar%20f%20g%20xs%20%3D%20filter%20f%20(map%20g%20xs) 该服务可以帮助你完成这些转换。 - Taylor Fausak

3

你可以使用 cabal install pointfree 命令行版本进行安装。如果你为它在 ghci 中定义了一个命名，那么就可以在 ghci 中使用它 :) https://hackage.haskell.org/package/pointfree - Jxek

@TaylorFausak，Blunt死了还是搬走了？ - dfeuer

@dfeuer 它已经死了。 - Taylor Fausak

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- luqui · Accepted Answer

转换为点无风格可以完全机械地完成，但如果不熟悉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

一个参数一个参数地处理。将左侧的参数移动到右侧的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合约"。
如果你有 \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

好了，现在在你的设备上试试吧！在决定使用哪个规则时并没有什么聪明才智可言：使用任何适用的规则都可以取得进展。