对 Haskell 还是没有入门。在文章 https://www.allstoalls.com/blog/blog/29 中提到一句话
有人可能会说 foldr 怎么就是迭代解法。我们认为 foldr 可以用 foldl 实现。 然后 foldl 是尾递归。可以等价为迭代处理。不是本文的主题，暂且不说
这真是一知半解，无知的话。
起因：那片文章最后的迭代 并不是像 《Combinatorial Generation》里面的迭代算法一样，只是 foldr 并不能直观看出是迭代算法。想看看是不是真的可以迭代出来。
文章最后得到：
cartProdN9 :: [[a]] -> [[a]]
cartProdN9 xss =
foldr h1 [[]] xss where
h1 xs yss = foldr g [] xs where
g x zss = foldr f zss yss where
f xs yss = (x:xs):yss
先讲 foldr 可以用 foldl 实现
foldl 的实现
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
使用 foldl 实现 foldr 得到：
foldr f e l = foldl (\g b x -> g (f b x)) id l e
用这个来替换 cardProd9 中的 foldr 得到
cartProdN10 :: [[a]] -> [[a]]
cartProdN10 xss =
foldl (\g b x -> g (h1 b x)) id xss [[]] where
h1 xs yss = foldl (\g b x -> g (g1 b x)) id xs [] where
g1 x zss = foldl (\g b x -> g (f b x)) id yss zss where
f xs wss = (x:xs):wss
这是在太丑陋了。
在 《Thinking Functionally with Haskell》 中有提到
只要满足
f x g (y z) = g (f x y) z
f x e = g e x
就有
foldr f e xs = foldl g e xs
我没有实际验证。但这么对称直接改动得到 （实际证明结果集满足算法，但返回顺序和 foldr 版本不同。所以其实我没有利用上面的公式，而是用对称性概念）：
cartProdN11 :: [[a]] -> [[a]]
cartProdN11 xss =
foldl h1 [[]] xss where
h1 yss xs = foldl g [] xs where
g zss x = foldl f zss yss where
f yss xs = (x:xs):yss
这样清爽多了。 以为要得到了验证，准备收手。不成想：
cartProdN11 [[1,2]| i <- [1 .. 1000]]
这个直接把 Haskell for Mac 跑挂了。
但是
cartProdN9 [[1,2]| i <- [1 .. 1000]]
居然秒出。这有点出乎我的意料。一番搜索找到 https://wiki.haskell.org/Foldr_Foldl_Foldl%27
换用文中的 foldl'
foldl' f z [] = z
foldl' f z (x:xs) = let z' = z `f` x
in z' `seq` foldl' f z' xs
但并没有解决问题。我依旧以为是 lazy 特性导致的问题。
继续搜索：https://www.fpcomplete.com/haskell/tutorial/all-about-strictness/
并采用其中的技术：
{-# LANGUAGE BangPatterns #-}
module D where
data StrictList a = Cons !a !(StrictList a) | Nil
strictMap :: (a -> b) -> StrictList a -> StrictList b
strictMap _ Nil = Nil
strictMap f (Cons a list) =
let !b = f a
!list' = strictMap f list
in b `seq` list' `seq` Cons b list'
strictEnum :: Int -> Int -> StrictList Int
strictEnum low high =
go low
where
go !x
| x == high = Cons x Nil
| otherwise = Cons x (go $! x + 1)
double :: Int -> Int
double !x = x * 2
list :: Int -> StrictList Int
list !x = Cons x (Cons x Nil)
foldlS = \f z l ->
case l of
Nil -> z
Cons !x !xs -> let !z' = z `f` x
in z' `seq` foldlS f z' xs
listlist :: StrictList (StrictList Int)
listlist = strictMap list $! strictEnum 1 100
myhead :: StrictList a -> a
myhead = \l ->
case l of
Cons x xs -> x
t :: Int
t = myhead (myhead listlist)
cartProdN12 :: StrictList (StrictList a) -> StrictList (StrictList a)
cartProdN12 xss =
foldlS h1 (Cons Nil Nil) xss where
h1 !yss !xs = foldlS g Nil xs where
g !zss !x = foldlS f zss yss where
f !yss !xs = Cons (Cons x xs ) yss
r = cartProdN12 listlist
hr :: Int
hr = myhead( myhead r)
依旧算不出来。
到此为止。 我已经没有思路了。由于是多层 foldl . 我的空间想象力无法得出结论。
我提了一个问题在 stackoverflow :
问题好像应该转换成： foldl 应该如何求出第一个结果 as fast as foldr.
再就是我的工具有问题： Haskell For Mac 算出第一个出来就不再算了 Lazy Lazy。给了我错误的诱导。