Haskell 表达式中没有函数的无点样式

Question

我一直在尝试将一些简单的函数转换成无点样式来练习。我从这样的事情开始：

zipSorted x y = (zip . sort) y $ sort x --zipSorted(x, y) = zip(sort(y), sort(x))

并最终将其转换为

zipSorted = flip (zip . sort) . sort

（我不确定这是否是最好的方法，但它确实有效）

现在我试图通过完全不依赖于 zip 和 sort 来进一步减少这个表达式。换句话说，我正在寻找这个函数：（如果我的词汇没有记错的话，我认为它是一个组合器）

P(f, g, x, y) = f(g(y), g(x))

sort 出现两次但只传入一次这一事实向我暗示我应该使用应用函子运算符 <*> 但由于某种原因我不知道如何使用。

根据我的理解，(f <*> g)(x) = f(x, g(x))，所以我尝试以这种形式重写第一个无点表达式：

flip (zip . sort) . sort
(.) (flip $ zip . sort) sort
(flip (.)) sort $ flip (zip . sort)
(flip (.)) sort $ flip $ (zip .) sort

好像sort应该是x，(flip (.))应该是f，flip . (zip .)应该是g。

p = (flip (.)) <*> (flip . (zip .))
p sort [2, 1, 3] [4, 1, 5]

按预期产生 [(1, 1), (4, 2), (5, 3)]，但现在我不知道如何将 zip 拉出来。我试过了

p = (flip (.)) <*> (flip . (.))
p zip sort [2, 1, 3] [4, 1, 5]

但这不起作用。有没有办法将该表达式转换为组合器，该组合器分解出 zip?

Answer 1

我只是向 lambdabot 询问了答案，而不是尝试手动解决：

<amalloy> @pl \zip sort x y -> (zip . sort) y $ sort x
<lambdabot> join . (((.) . flip) .) . (.)

Answer 2

让我们从头说起：

zipSort x y = zip (sort y) (sort x)

它以相反的顺序使用它的参数有点奇怪，但我们稍后可以用 flip 来解决这个问题。

这里我们有两个参数的 "combining" 函数的一般模式（此处：zip）被传递两个由另一个函数转换的值。如果我们有相同的基本参数但不同的转换器，这将是一个 liftA2 模式：

  c (f x) (g x)
==
  liftA2 c f g x

但这里恰恰相反：我们在两边都有相同的转换函数（此处：sort），但参数不同（x 和 y）。那是 on:

  c (f x) (f y)
==
  (c `on` f) x y

在你的情况下我们得到：

zip (sort y) (sort x)
(zip `on` sort) y x
flip (zip `on` sort) x y

所以

zipSort = flip (zip `on` sort)  -- or: flip (on zip sort)

我们可以进一步提取zip和sort通过识别标准two-argument-into-one-argument-function组成：

(\x y -> f (g x y)) == (f .) . g

给予

zipSort = ((flip .) . on) zip sort

请注意，此功能不如 pointful 版本通用。原始函数的类型为

(Ord a, Ord b) => [a] -> [b] -> [(b, a)]

但 pointfree 版本有类型

(Ord a) => [a] -> [a] -> [(a, a)]

因为统一两个 sort 强制它们具有相同的类型。

Haskell point-free style with no functions in the expression