瑞典语的问候语有多瑞典语？

Question

考虑以下 Haskell 定义，摘自 this excellent Haskell video on YouTube：

import Data.List
greeting = "Hello"
swedish = intersperse 'f'
very f x = f (f (f x))

如果我们将它们加载到 GHCi 中，我们会看到以下结果：

ghci> swedish greeting
"Hfeflflfo"
ghci> very swedish greeting
"Hfffffffeffffffflffffffflfffffffo"
ghci> very very swedish greeting
"Hffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
fffffffffffffffffffffffffffff... (536,870,913 chars total)

前两个输出我完全理解。一个 swedish greeting 散布在 f 中，而一个 very swedish greeting 只是一个 swedish (swedish (swedish greeting))，它散布三重。

但是第三行输入到底发生了什么？我（相当不完整）对 Haskell 语法的理解表明，space 分隔的表达式序列被解释为函数调用，其中第一个表达式是函数，其余是参数。在那种情况下，当最外层的 very 仅定义为接受两个参数时，如何使用三个参数（very、swedish 和 greeting）调用它？

如果有帮助，似乎 very very swedish greeting 等同于 swedish $ swedish $ swedish $ swedish $ ... (27 layers of swedish) ... $ swedish $ swedish greeting。

Answer 1

函数应用是左关联的，所以

very very swedish greeting

等同于

((very very) swedish) greeting

very 的类型为 (t -> t) -> t -> t。 very 可以作为第一个参数传递给 very

very      :: (t        -> t       ) -> t        -> t
     very ::  (t -> t) -> (t -> t)
very very ::                           (t -> t) -> (t -> t)

very very 也是一个函数，它的类型是 (t -> t) -> t -> t。由于 swedish 的类型为 String -> String，因此可以将其传递给 very very。结果函数的类型为 String -> String

((very very) swedish) :: String -> String

类型为 String -> String 的函数可以应用于 greeting :: String

(((very very) swedish) greeting) :: String

Answer 2

你说：

My (rather incomplete) understanding of Haskell syntax says that a space-separated sequence of expressions is interpreted as a function call, where the first expression is the function and the rest are the arguments.

你是对的，这不是对实际发生的事情的完整理解。从你的例子：

very very swedish greeting

这等同于：

((very very) swedish) greeting

这是因为函数应用程序是左关联的。此外，Haskell 中的每个函数都有一个输入，return 有一个结果。您认为接受多个输入的函数实际上是接受单个输入的函数，return 一个函数作为它们的结果。

这也解释了为什么箭头 (->) 分隔函数输入和导致函数类型。考虑 ++ 的类型：

(++) :: [a] -> [a] -> [a]

这等同于：

(++) :: [a] -> ([a] -> [a])

您可能认为 ++ 运算符采用两个列表并 returning 一个列表，但实际上它是一个输入（列表）的函数 return是一个输入（另一个列表）的函数，return是一个列表。

综上所述，您有望看到 very very 本身就是一个有效的表达式（并且恰好与 very 具有相同的类型）。

very very x

相当于：

very (very (very x))

Answer 3

Daniel Pratt 的回答解释了句法层面上发生的事情。但是为什么 (very very) 会导致 swedish 被应用 27 次而不是其他数字？为了解决这个问题，让我们创建一个比 very 更通用的函数，它应用函数 n 次：

-- Takes number of times to apply `n` and a function `f`, and returns a
-- function that applies `f` `n` times.
appn n f
  | n == 1    = f
  | otherwise = f . (appn (n - 1) f)

-- If necessary, you could define very = (appn 3)
very = (appn 3)

并且让我们停止使用 swedish 而是使用 (+1) 这样可以更容易地计算函数被应用了多少次：

Vandelay Industries> (appn 3) (appn 3) (+1) 0
27
Vandelay Industries> (appn 2) (appn 3) (+1) 0
9
Vandelay Industries> (appn 2) (appn 4) (+1) 0
16
Vandelay Industries> (appn 4) (appn 10) (+1) 0
10000
Vandelay Industries> (appn 2) (appn 2) (appn 2) (+1) 0
16

你现在可以看到模式了。 (appn x) (appn y) 生成 appn $ y ^ x 的等价物。但为什么？考虑 (appn 2) (appn 3)。 (appn 3) 表示 f (f (f x)) 或 f . f . f。通过 (appn 2)，每个 f 实际上应用了 3 次：(f . f . f) . (f . f . f) . (f . f . f) 或总共 9 次。

瑞典语的问候语有多瑞典语？

How swedish is a very very swedish greeting?

haskell

composition

higher-order-functions