haskell - 具有匿名功能的 Haskell Fold

Question

我对 Haskell 基础之一有疑问：折叠 + 匿名函数

我正在开发一个 bin2dec 程序foldl。
解决方案如下所示：

bin2dec :: String -> Int
bin2dec = foldl (\x y -> if y=='1' then x*2 + 1 else x*2) 0

我了解foldl/的基本概念，foldr但我不明白参数x y代表什么。

Answer 1

查看类型foldl

foldl :: (a -> b -> a) -> a -> [b] -> a

考虑foldl f z list

所以 foldl 基本上在列表（或任何可折叠的东西）上递增地工作，从左侧获取 1 个元素并应用f z element以获取用于下一步的新元素，同时折叠其余元素。基本上对 foldl 的一个简单定义可能有助于理解它。

 foldl f z []     = z
 foldl f z (x:xs) = foldl f (f z x) xs

Haskell wiki中的图表可能有助于建立更好的直觉。

考虑您的功能f = (\x y -> if y=='1' then x*2 + 1 else x*2)并尝试为foldl f 0 "11". 这里"11"是一样的['1','1']

  foldl f 0 ['1','1'] 
= foldl f (f 0 '1') ['1']

现在 f 是一个接受 2 个参数的函数，第一个是整数，第二个是字符并返回一个整数。所以 在这种情况下x=0和y='1'，所以f x y = 0*2 + 1 = 1

= foldl f 1 ['1']
= foldl f (f 1 '1') []

现在再次申请f 1 '1'。这里x=1等等。y='1'_f x y = 1*2 + 1 = 3

= foldl f 3 [] 

使用空列表的第一个定义foldl。

= 3 

这是“11”的十进制表示。

Answer 2

使用类型！您可以键入:tGHCi，然后键入任何函数或值以查看其类型。如果我们询问类型，会发生以下情况foldl

Prelude> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a

输入列表的类型为[b]，因此它是bs 的列表。输出类型是a，这是我们要生成的。您还必须为折叠提供一个初始值，类型也是a。函数是类型

a -> b -> a

第一个参数 ( a) 是到目前为止计算的折叠值。第二个参数 ( b) 是列表的下一个元素。所以在你的例子中

\x y -> if y == '1' then x * 2 + 1 else x * 2

参数x是您到目前为止计算的二进制数，并且y是列表中的下一个字符（ a'1'或 a '0'）。