Haskell函数应用和currying

Question

我总是对学习新语言感兴趣,这一事实让我保持警惕,让我(我相信)成为更好的程序员.我征服Haskell的尝试来了又走 - 到目前为止两次 - 我决定是时候再试一次.第三次是魅力吧？

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

上次让我失去信心的问题很简单:整数的排列.即从整数列表到列表列表 - 列表的排列:

[int] -> [[int]]

这实际上是一个普遍的问题,因此用'a'替换上面的'int'仍然适用.

从我的笔记:

我先自己编码,然后成功.欢呼!

我将我的解决方案发送给我的一位好朋友--Haskell大师,通常有助于向大师学习 - 他告诉我这个,据我所知,"表达了语言的真正力量,使用通用设施来编码你的需要".所有这一切,我最近喝了kool-aid,让我们走吧:

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"的第二行,但是OK:它将第一个arg置于列表中的所有可能位置.凉.

现在,了解foldr和concatMap.在"真实世界Haskell"中,DOT被解释了......

(f . g) x

...作为......的另一种语法

f (g x) 

在大师发送的代码中,DOT用于折叠器,"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 (g x)我们可以减少到(f (g x)) y,这也是相同的f (g x) y.

所以(concatMap . ins) 1 [[2,3]]相当于concatMap (ins 1) [[2,3]].这里没有魔力.

另一种解决方法是通过以下类型:

.有类型(b -> c) -> (a -> b) -> a -> 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 . insis 的类型t -> [[t]] -> [[t]],意味着一个函数接受任何一个列表(whatevers)并返回一个列表列表(相同类型).

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,以1和[[2, 3]]-完全不同的,因为你用Haskell的可怕错误消息想通了.

更新:进一步强调这一点.你说那(f . g) x是另一种语法f (g x).这是错的!.仅仅是一个函数,函数可以具有非字母数字名称(>><,..等等,也可以是函数名).

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 . map,但事实并非如此.同样,它可能看起来像concatMap f = concat . (map f),但这也不是真的.等式推理会告诉你原因.