Chinaunix

标题: Haskell-Cafe 上一个关于生成 stream 问题的解答 [打印本页]

作者: MMMIX 时间: 2009-06-19 22:39
标题: Haskell-Cafe 上一个关于生成 stream 问题的解答
GüŸnther Schmidt 在 Haskell-Cafe 上问如何生成像下面这样的 stream

["a", "b", "c" .. "z", "aa", "ab", "ac" .. "az", "ba", "bb", "bc" .. "bz", "ca" ...]

大家给出了各种个样的解答，下面两个特别有意思：

Reid Barton 的：

concatMap (\n -> replicateM n ['a'..'z']) [1..]

复制代码

Matthew Brecknell 的：

tail $ concat $ iterate (map (:) ['a'..'z'] <*>) [[]]

复制代码

这两个看似差异很大的解答其实是一回事，只不过表示形式不同罢了。感兴趣的可以推导一下

讨论的地址：
http://www.haskell.org/pipermail ... 09-June/062940.html

作者: sw2wolf 时间: 2009-06-21 11:19
>>concatMap (\n -> replicateM n ['a'..'z']) [1..]
好理解

>>tail $ concat $ iterate (map (:) ['a'..'z'] <*>) [[]]
不好理解

作者: MMMIX 时间: 2009-06-21 11:34

原帖由 sw2wolf 于 2009-6-21 11:19 发表
>>concatMap (\n -> replicateM n ['a'..'z']) [1..]
好理解

>>tail $ concat $ iterate (map (:) ['a'..'z'] <*>) [[]]
不好理解

我的感觉正好相反，后者的逻辑要简单多了。

作者: sw2wolf 时间: 2009-06-21 14:41

原帖由 MMMIX 于 2009-6-21 11:34 发表

我的感觉正好相反，后者的逻辑要简单多了。

能解释一下后者吗？谢谢！

作者: MMMIX 时间: 2009-06-21 16:20

原帖由 sw2wolf 于 2009-6-21 14:41 发表

能解释一下后者吗？谢谢！

Sure.

map (:) ['a' .. 'z'] <*>
= (map (:) ['a' .. 'z']) <*>
= [('a':), ..., ('z':)] <*> -- misuse of [...] notation

复制代码

这个函数作用在 ms :: [[a]] 上的结果为：

(map ('a':) ms) ++ (map ('b':) ms) ++ ... ++ (map ('z':) ms)

也即对 list 来说， (<*>) 左边是一列函数，右边是一列成员为 list 的 list，(<*>) 将左边的函数依次作用在右边 list 上得到一个新的 list，然后把这些新 list 合并就是结果。

BTW, 说说你为什么觉得第一种解法好理解吧。

作者: sw2wolf 时间: 2009-06-22 09:13
对于concatMap (\n -> replicateM n ['a'..'z']) [1..], 我是这样理解的:(为了好说明, 我将范围定为'a'..'c')

replicateM 1 ['a'..'c'] = ["a","b","c"]
replicateM 2 ['a'..'c'] = ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
replicateM 3 ['a'..'c'] = ["aaa","aab","aac","aba","abb","abc","aca","acb","acc","baa","bab","bac","bba","bbb","bbc","bca","bcb","bcc","caa","cab","cac","cba","cbb","cbc","cca","ccb","ccc"]
......
然后再将这些list合并就可以了.

BTW,
:m Control.Applicative
Prelude Control.Applicative> :i <*>
class (Functor f) => Applicative f where
  ...
  (<*>) :: f (a -> b) -> f a -> f b
    -- Defined in Control.Applicative
infixl 4 <*>

主要对<*>不太明白 !

作者: MMMIX 时间: 2009-06-22 09:31

原帖由 sw2wolf 于 2009-6-22 09:13 发表
对于concatMap (\n -> replicateM n ['a'..'z']) [1..], 我是这样理解的:(为了好说明, 我将范围定为'a'..'c')

如果你能将 ['a' .. 'z'] 看作一组 action，那么这两个解答一样的好理解。事实上，这两个解答是等价的，因为对于 xs::[[a]]
replicateM n xs = (iterate (map (:) xs <*>) [[]]) !! n

作者: MMMIX 时间: 2009-06-22 09:34

原帖由 sw2wolf 于 2009-6-22 09:13 发表
对于concatMap (\n -> replicateM n ['a'..'z']) [1..], 我是这样理解的为了好说明, 我将范围定为'a'..'c')

replicateM 1 ['a'..'c'] = ["a","b","c"]

其实这个解答难就难在从 replicateM 1 ['a' .. 'z'] 到 ["a", ..., "z"] 这一步，如果这步走通了，那就很好理解了。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)