Haskell 函数应用和柯里化

Question

我总是对学习新语言感兴趣，这一事实让我保持警惕，并使我（我相信）成为一个更好的程序员。我征服 Haskell 的尝试来了又去——到目前为止已经两次了——我决定是时候再试一次了。第三次就有魅力了，对吧？

没有。我重新阅读了我的旧笔记......并感到失望:-(

上次让我失去信心的问题很简单：整数的排列。 即从整数列表到列表列表 - 它们的排列列表：

[int] -> [[int]]

这实际上是一个通用问题，因此将上面的“int”替换为“a”仍然适用。

根据我的笔记：

我首先自己编写代码，我成功了。欢呼！

我将我的解决方案发送给我的一个好朋友 - Haskell 大师，它通常有助于向大师学习 - 他向我发送了这个，我被告知，“表达了语言的真正力量，使用通用设施来编码你的代码需要”。总而言之，我最近喝了酷爱饮料，走吧：

permute :: [a] -> [[a]]
permute = foldr (concatMap.ins) [[]]
   where ins x []     = [[x]]
         ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

嗯。 让我们来分解一下：

bash$ cat b.hs
ins x []     = [[x]]
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

bash$ ghci
Prelude> :load b.hs
[1 of 1] Compiling Main             ( b.hs, interpreted )
Ok, modules loaded: Main.

*Main> ins 1 [2,3]
[[1,2,3],[2,1,3],[2,3,1]]

好的，到目前为止，一切都很好。我花了一分钟才理解“ins”的第二行，但是还好： 它将第一个参数放置在列表中所有可能的位置。凉爽的。

现在，来了解foldr 和concatMap。在“现实世界 Haskell”中，DOT 被解释

(f . g) x

为... ...只是另一种语法...

f (g x) 

并且在大师发送的代码中，DOT 是从foldr 中使用的，其中“ins”函数作为折叠“崩溃”：

*Main> let g=concatMap . ins
*Main> g 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

好的，因为我想了解大师如何使用DOT，所以我根据DOT定义尝试等效表达式，(f . g) x = f (gx) ...

*Main> concatMap (ins 1 [[2,3]])

<interactive>:1:11:
     Couldn't match expected type `a -> [b]'
            against inferred type `[[[t]]]'
     In the first argument of `concatMap', namely `(ins 1 [[2, 3]])'
     In the expression: concatMap (ins 1 [[2, 3]])
     In the definition of `it': it = concatMap (ins 1 [[2, 3]])

什么！？！为什么？ 好的，我检查了 concatMap 的签名，发现它需要一个 lambda 和一个列表，但这就是 只是人类的思维； GHC 如何应对？根据上面 DOT 的定义...

(f.g)x = f(g x), 

...我所做的是有效的，替换方面：

(concatMap . ins) x y = concatMap (ins x y)

挠头...

*Main> concatMap (ins 1) [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

所以... DOT 的解释显然是 太简单了... DOT 必须足够聪明才能理解 事实上，我们希望“ins”被咖喱掉并“吃掉”第一个 参数 - 从而成为只想对 [t] 进行操作的函数 （并在所有可能的位置上用“1”“散布”它们）。

但这是在哪里指定的呢？ 时，GHC 如何知道这样做

*Main> (concatMap . ins) 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

当我们调用： “ins”签名是否以某种方式传达了这个......“吃掉我的第一个论点”政策

*Main> :info ins
ins :: t -> [t] -> [[t]]        -- Defined at b.hs:1:0-2

？我没有看到什么特别的 - “ins”是一个带有“t”的函数， 't' 列表，并继续创建包含所有“interspersals”的列表。没有什么“吃掉你的第一个论点并将其消除”。

所以……我很困惑。我明白（在查看代码一个小时后！）发生了什么，但是……万能的上帝……也许 GHC 试图看看它可以“剥离”多少参数？

  let's try with no argument "curried" into "ins",
  oh gosh, boom, 
  let's try with one argument "curried" into "ins",
  yep, works,
  that must be it, proceed)

再说一次 - 哎呀......

由于我总是将我正在学习的语言与我已经知道的语言进行比较，“ins”在 Python 中看起来如何？

a=[2,3]
print [a[:x]+[1]+a[x:] for x in xrange(len(a)+1)]

[[1, 2, 3], [2, 1, 3], [2, 3, 1]]

老实说，现在...哪个更简单？

我的意思是，我知道我是 Haskell 的新手，但我感觉自己像个白痴……看了 4 行代码一个小时，最后假设编译器……尝试各种解释，直到找到“点击”？

引用《致命武器》的话，“我太老了，做不了这个”……

Answer 1

(f . g) x = f (g x)

这是真实的。你由此得出结论，这

(f . g) x y = f (g x y)

也一定是正确的，但事实并非如此。事实上，以下情况是正确的：

(f . g) x y = f (g x) y

这是不一样的。

为什么这是真的？那么 (f . g) x y 与 ((f . g) x) y 相同，因为我们知道 (f . g) x = f (gx) 我们可以将其简化为 (f (gx)) y，这又与 f (gx) y 相同。

因此 (concatMap . ins) 1 [[2,3]] 相当于 concatMap (ins 1) [[2,3]]。这里没有发生任何魔法。

解决此问题的另一种方法是通过类型：

. 的类型为 (b -> c) -> (a→b)→一个-> c，concatMap 的类型为 (x -> [y]) -> [x]-> [y], ins 的类型为 t -> [t]-> [[t]]。因此，如果我们使用 concatMap 作为 b -> c 参数和 ins 作为 a ->; b 参数，则 a 变为 t，b 变为 [t] -> [[t]] 和 c 变为 [[t]] -> [[t]]（其中 x = [t] 和 y = [t] ）。

所以是 concatMap 的类型。 ins 是 t -> [[t]]-> [[t]]，这意味着一个函数接受一个whatever和一个列表列表（无论什么）并返回一个列表列表（相同类型）。

Answer 2

我想补充我的两分钱。这个问题和答案听起来像是 . 是一些神奇的运算符，它通过重新安排函数调用来完成奇怪的事情。事实并非如此。 . 只是函数组合。下面是 Python 中的一个实现：

def dot(f, g):
    def result(arg):
        return f(g(arg))
    return result

它只是创建一个新函数，将 g 应用于参数，将 f 应用于结果，并返回应用 f< 的结果/代码>。

所以 (concatMap . ins) 1 [[2, 3]] 的意思是：创建一个函数 concatMap 。 ins，并将其应用于参数 1 和 [[2, 3]]。当您执行 concatMap (ins 1 [[2,3]]) 时，您实际上是在说，将函数 concatMap 应用于应用 ins 的结果code> 到 1 和 [[2, 3]] - 完全不同，正如您通过 Haskell 的可怕错误消息所发现的那样。

更新：进一步强调这一点。您说 (f . g) x 是 f (gx) 的另一种语法。这是错误！ . 只是一个函数，因为函数可以具有非字母数字名称（>><、.. 等）。 ，也可以是函数名称）。

Answer 3

这个问题你想太多了。您可以使用简单的等式推理来解决所有问题。让我们从头开始尝试一下：

permute = foldr (concatMap . ins) [[]]

这可以简单地转换为：

permute lst = foldr (concatMap . ins) [[]] lst

concatMap 可以定义为：

concatMap f lst = concat (map f lst)

foldr 在列表上工作的方式是（例如）：

-- let lst = [x, y, z]
foldr f init lst
= foldr f init [x, y, z]
= foldr f init (x : y : z : [])
= f x (f y (f z init))

所以类似

permute [1, 2, 3]

变为：

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 
    ((concatMap . ins) 2
       ((concatMap . ins) 3 [[]]))

让我们完成第一个表达式：

(concatMap . ins) 3 [[]]
= (\x -> concatMap (ins x)) 3 [[]]  -- definition of (.)
= (concatMap (ins 3)) [[]]
= concatMap (ins 3) [[]]     -- parens are unnecessary
= concat (map (ins 3) [[]])  -- definition of concatMap

现在 ins 3 [] == [3]，所以

map (ins 3) [[]] == (ins 3 []) : []  -- definition of map
= [3] : []
= [[3]]

所以我们的原始表达式变为：

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 
    ((concatMap . ins) 2
       ((concatMap . ins) 3 [[]]))
= (concatMap . ins) 1 
    ((concatMap . ins) 2 [[3]]

让我们完成

(concatMap . ins) 2 [[3]]
= (\x -> concatMap (ins x)) 2 [[3]]
= (concatMap (ins 2)) [[3]]
= concatMap (ins 2) [[3]]     -- parens are unnecessary
= concat (map (ins 2) [[3]])  -- definition of concatMap
= concat (ins 2 [3] : [])
= concat ([[2, 3], [3, 2]] : [])
= concat [[[2, 3], [3, 2]]]
= [[2, 3], [3, 2]]

所以我们的原始表达式变为：

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 [[2, 3], [3, 2]]
= (\x -> concatMap (ins x)) 1 [[2, 3], [3, 2]]
= concatMap (ins 1) [[2, 3], [3, 2]]
= concat (map (ins 1) [[2, 3], [3, 2]])
= concat [ins 1 [2, 3], ins 1 [3, 2]] -- definition of map
= concat [[[1, 2, 3], [2, 1, 3], [2, 3, 1]], 
          [[1, 3, 2], [3, 1, 2], [3, 2, 1]]]  -- defn of ins
= [[1, 2, 3], [2, 1, 3], [2, 3, 1], 
   [1, 3, 2], [3, 1, 2], [3, 2, 1]]

这里没什么神奇的。我认为您可能感到困惑，因为很容易假设 concatMap = concat 。地图，但事实并非如此。同样，它可能看起来像 concatMap f = concat 。 (map f)，但这也不是真的。等式推理会告诉你原因。