Haskell-Cafe 上一個關(guān)于生成 stream 問題的解答

MMMIX

GüŸnther Schmidt 在 Haskell-Cafe 上問如何生成像下面這樣的 stream

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

大家給出了各種個樣的解答，下面兩個特別有意思：

Reid Barton 的：

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

復(fù)制代碼

Matthew Brecknell 的：

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

復(fù)制代碼

這兩個看似差異很大的解答其實是一回事，只不過表示形式不同罷了。感興趣的可以推導(dǎo)一下

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

sw2wolf

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

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

MMMIX

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

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

我的感覺正好相反，后者的邏輯要簡單多了。

sw2wolf

原帖由 MMMIX 于 2009-6-21 11:34 發(fā)表

我的感覺正好相反，后者的邏輯要簡單多了。

能解釋一下后者嗎？ 謝謝！

MMMIX

原帖由 sw2wolf 于 2009-6-21 14:41 發(fā)表


能解釋一下后者嗎？ 謝謝！

Sure.

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

復(fù)制代碼

這個函數(shù)作用在 ms :: [[a]] 上的結(jié)果為：

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

也即對 list 來說， (<*>) 左邊是一列函數(shù)，右邊是一列成員為 list 的 list，(<*>) 將左邊的函數(shù)依次作用在右邊 list 上得到一個新的 list，然后把這些新 list 合并就是結(jié)果。

BTW, 說說你為什么覺得第一種解法好理解吧。

sw2wolf

對于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

原帖由 sw2wolf 于 2009-6-22 09:13 發(fā)表
對于concatMap (\n -> replicateM n ['a'..'z']) [1..], 我是這樣理解的:(為了好說明, 我將范圍定為'a'..'c')

如果你能將 ['a' .. 'z'] 看作一組 action，那么這兩個解答一樣的好理解。事實上，這兩個解答是等價的，因為對于 xs::[[a]]
replicateM n xs = (iterate (map (:) xs <*>) [[]]) !! n

MMMIX

原帖由 sw2wolf 于 2009-6-22 09:13 發(fā)表
對于concatMap (\n -> replicateM n ['a'..'z']) [1..], 我是這樣理解的為了好說明, 我將范圍定為'a'..'c')

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

其實這個解答難就難在從 replicateM 1 ['a' .. 'z'] 到 ["a", ..., "z"] 這一步，如果這步走通了，那就很好理解了。