启发自： 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 ```

笛卡尔积的递归和迭代算法