启发自： Mary Sheeran, Chalmer 的演讲 In praise of Higher Order Functions and of some friends and heroes 。我觉得推导的不直观。而且跳跃性太大。自己重新推导了一遍。
递归版
cartProdN1 :: [[a]] -> [[a]]
cartProdN1 [] = [[]]
cartProdN1 (xs:yss) = [ x:ys | x <- xs, ys <- cartProdN1 yss ]
迭代版：
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
其中 h1 一个一个处理 xs 和 聚合结果。
然后 xs 又是一个 list 。对 xs 而言也需要 遍历处理。然后处理 xs 的每一个元素的时候。
有人可能会说 foldr 怎么就是迭代解法。我们认为 foldr 可以用 foldl 实现。 然后 foldl 是尾递归。可以等价为迭代处理。不是本文的主题，暂且不说。
推导如下：
cartProdN1' :: [[a]] -> [[a]]
cartProdN1' xss =
h xss where
h [] = [[]]
h (xs:yss) = [ x:ys | x <- xs, ys <- h yss ]
化 haskell 的模式匹配到一个函数。起名 cartPordN1'， 因为比较直观没有用到什么技巧。
提取 (h yss) 为 yss 也比较直观
cartProdN1'' :: [[a]] -> [[a]]
cartProdN1'' xss =
h xss where
h [] = [[]]
h (xs:yss) = g xs (h yss) where
g xs yss = [x:ys | x <- xs, ys <- yss]
看一下 foldr 的结构
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
h 遍历 xss 和 foldr f 结构一样。
cartProdN2 :: [[a]] -> [[a]]
cartProdN2 xss =
foldr h [[]] xss where
h xs yss = [x:ys | x <- xs, ys <- yss]
列表展开的定义 。 第一个元素和 后面所有的匹配。加上后面整体的结果。
cartProdN3 :: [[a]] -> [[a]]
cartProdN3 xss =
foldr h [[]] xss where
h (x:xs) yss =
map (x:) yss ++ [x:ys| x <- xs, ys <- yss]
然后可以识别出列表推导就是 h 自己的一个调用 [x:ys| x <- xs, ys <- yss] = h xs yss 。而且替换成 h ，h 变成了递归函数，必须要有 base case。
cartProdN4 :: [[a]] -> [[a]]
cartProdN4 xss =
foldr h [[]] xss where
h [] yss = []
h (x:xs) yss = (map (x:) yss) ++ (h xs yss)
使用演讲中的 mapa
mapa :: (b -> a) -> [a] -> [b] -> [a]
mapa g z l = (map g l) ++ z
替换得到
cartProdN5 :: [[a]] -> [[a]]
cartProdN5 xss =
foldr h [[]] xss where
h [] yss = []
h (x:xs) yss = mapa (x:) (h xs yss) yss
观察 mapa 的结构 。 z 当作累积参数可以提前被追加。
mapa :: (b -> a) -> [a] -> [b] -> [a]
mapa g z l = foldr f z l where
f x y = (g x):y
替换 mapa 为 foldr 得到。
cartProdN6 :: [[a]] -> [[a]]
cartProdN6 xss =
foldr h [[]] xss where
h [] yss = []
h (x:xs) yss = foldr f (h xs yss) yss where
f xs yss = (x:xs):yss
其中 mapa 中的 g = (x:) ; x = xs ; z = yss; z = (h xs yss); y = yss (这是 f 的参数 yss ，注意和 foldr 的参数 yss 区别)
这里并没有结束。 h 这里递归函数。并不是迭代。我们的目的是消除递归调用。
消除递归调用 h 的方法。就是 h 提取出来。引入辅助函数。
cartProdN7 :: [[a]] -> [[a]]
cartProdN7 xss =
foldr h [[]] xss where
h xs yss = h' xs
where
h' [] = []
h' (x:xs) = foldr f (h' xs) yss where
f xs yss = (x:xs):yss
cardPord6 和 cardProd7 为什么等价。 这一块没有想好怎么描述。 看起来也不直观。 等待后续继续观察。。。
继续引入辅助函数 g . 这一步相对直观， 就是把 foldr f 抽离出来。
cartProdN8 :: [[a]] -> [[a]]
cartProdN8 xss =
foldr h1 [[]] xss where
h1 xs yss = h' xs
where
h' [] = []
h' (x:xs) = g x (h' xs)
g x zss = foldr f zss yss
where
f xs yss = (x:xs):yss
可以发现。 h' 本身就符合 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
g 就是 h' foldr 化的 参数 f 。
cardProdN6 -> cardProdN7 还是想解释一下。但发现自己只能用 python 描述了。
def f(xs, yss):
if xs == []:
return []
x xs <- xs
return foldr g (f xs) yss
def f(xs, yss):
def f'(xs):
if xs == []:
return []
x xs <- xs
return foldr g (f' xs) yss
return f' xs