Haskell 列表长度函数

Question

要使用 foldr 计算列表的长度，可以这样做：

foldr (\_ acc -> acc + 1) 0

进一步扩展折叠函数需要增加第二个参数的想法，我想到了这个（这是错误的）：

foldr ((+1) . (flip const)) 0`

对该类型的进一步检查揭示了这一点：

(+1) . (flip const) :: Num (c -> c) => a -> c -> c

Haskell higher order function to calculate length 该页面上有一个有趣的评论，我真的无法理解

foldr (((+1).).(flip const)) 0

谁能解释一下这个组合实际上是如何工作的？

Answer 1

首先，让我们关注一下为什么foldr ((+1) . (flip const)) 0是错误的。您只想增加第二个参数而忘记第一个参数。从语义上讲，那是

\_ a -> a + 1

但是，您写了以下内容：

(+1) . flip const
= (+1) . (\_ a -> a)
= \x -> (+1) . (\_ a -> a) $ x
= \x -> (+1) $ (\_ a -> a) $ x
= \x -> (+1) $ \a -> a
= \_ -> (+1) (\a -> a)
= const ( (+1) (\a -> a))

这就是您突然需要 Num (c -> c) 的原因，因为您正试图在 id 上应用 (+1)。

但你实际上是指：

\_ a -> a + 1
= \_ a -> (+1) a
= \_   -> (+1)
= const (+1)

毕竟，您想忘记第一个参数并在第二个参数上使用函数 f。您所要做的就是使用 const f.

组合 ((+1).).(flip const) 过于冗长，可能由 pointfree:

生成

((+1).).(flip const)
= ((\x -> x + 1).) . (\a _ -> a)
= \c -> ((\x -> x + 1).) . (\a _ -> a) $ c
= \c -> ((\x -> x + 1).) $ \_ -> c
= \c -> \f -> (\x -> x + 1) . f $ \_ -> c
= \c ->   (\x -> x + 1) . \_ -> c
= \_ c -> (\x -> x + 1) $ c
= \_ c -> c + 1

Answer 2

这确实是一条评论，但对一个人来说太长了。

除非你要处理像惰性 Nats 这样的奇怪数字，否则你真的想要

length xs = foldl' (\acc _ -> 1 + acc) 0 xs

让这变得毫无意义，

length = foldl' (\acc -> const ((1+) acc)) 0
length = foldl' (const . (1+)) 0

如果愿意，您可以将原始 foldl' 表达式转换为 foldr 形式，如下所示：

length xs = foldr go id xs 0 where
  go _ r acc = r $! 1 + acc

正在咀嚼 go，

go _ r acc = ($!) r $ (+) 1 acc
go _ r = ($!) r . (+1)
go _ r = (. (+1)) (($!) r)
go _ = (. (+1)) . ($!)
go = const ((. (+1)) . ($!))

正在咀嚼 length、

length = flip (foldr go id) 0

综合起来，

length = flip (foldr (const ((. (+1)) . ($!))) id) 0

首先，我发现这个 point-free 表格完全不透明。

Haskell 列表长度函数

Haskell function for list length

haskell

fold