使用foldr实现Haskell foldl

Question

我很难理解使用foldr实现foldl函数。我读过这个问题（用foldr写foldl），在下面的例子中我仍然有一些不理解的地方：

fun :: [Int] -> [Int]
fun l = foldr g (const []) l 1
    where g x f lst = if gcd x lst == 1 then x : f x else f lst

函数将一个列表作为参数，并返回另一个列表，其中gcd(l[i], l[i + 1] = 1。

我的问题如下：
1.x、f和lst是谁
2.什么是const[]，为什么我不能使用id功能？

Answer 1

foldr是一种奇怪的工具，比如自行车，一旦掌握了窍门，就很容易使用，但从一开始就很难学习。经过几年的经验，我已经非常善于发现我可以用foldr解决的问题，并立即正确地解决这些问题，但我很容易需要一段时间才能弄清楚我做了什么，并详细解释！

从实践的角度来看，我通常用模糊的延续传递语言来思考foldr。忽略foldr仅应用于三个参数的"简单"情况，foldr的应用程序如下所示：

foldr go finish xs acc1 acc2 ... where
  finish acc1 acc2 ... = ?
  go x cont acc1 acc2 ... = ?

acc1等是"从左到右"传递的累加器。从概念上讲，结果由"从右到左"传递的单个值组成。

finish获取累加器的最终值，并产生某种结果类型。这通常是最容易写的部分，因为

foldr go finish [] acc1 acc2 ...
=
finish acc1 acc2 ...

因此，一旦你弄清楚了你想要你的折叠产生什么，写finish就相当机械了。

go获取一个容器元素、一个"continuation"和累加器。如果这些累加器"转发"到continuation以获得结果，则它会传递修改后的值，并使用该结果构造自己的结果。

foldl是一个特别简单的情况，因为它的go函数只返回通过使用新的累加器参数折叠容器的其余部分而得到的结果。我认为看一个做得更多的例子更有启发性。这是一个使用数字容器并生成一个对列表的函数，这些对表示一个正在运行的和和和一个正在进行的乘积。

sumsProducts :: (Num n, Foldable f) => f n -> [(n, n)]
sumsProducts xs = foldr go finish xs 0 1
  where
    finish total prod = [(total, prod)]
    go x cont total prod =
      (total, prod) : cont (x + total) (x * prod) 

Answer 2

foldr的类型签名是这个

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

这意味着应用于其3个参数的foldr必须返回一个将1作为参数的函数。

因此，您可以将foldr专门用于此

foldr :: (Int -> (Int -> [Int]) -> (Int -> [Int])) 
        -> (Int -> [Int]) 
        -> [Int]
        -> (Int -> [Int])

这意味着您的g功能必须具有以下类型的

g :: Int -> (Int -> [Int]) -> Int -> [Int] 

所以你的参数是类型

x   :: Int
f    :: Int -> [Int]
lst :: Int

foldr在它的第二个参数中需要一个Int -> [Int]，而不仅仅是Int，所以不能向它传递值[]。

幸运的是，const返回了一个忽略其参数的函数，并且总是返回一个常量表达式

const [] :: a -> [b]

在您的情况下，f实际上是某种累加器。但是，您不是将值列表缩减为某个数字，而是在此处链接函数。最后，通过将1传递给这个函数链，它将得到评估，然后构建您在fun中返回的实际列表。