Haskell函数用于列表长度

Question

要使用foldr计算列表的长度,可以执行以下操作:

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

进一步扩展折叠函数需要增加第二个参数的想法,我想出了这个(这是错误的):

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

进一步检查该类型揭示了这一点:

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

Haskell高阶函数计算长度 在该页面上有一个有趣的评论,我真的无法理解

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),因为你想申请(+1)上id.

但你实际上意味着:

\_ 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