List comprehension和递归的巧妙结合

我以前总以为list comprehension这个语法糖不过就是些map,filter转换罢了，最近看到Haskell和Erlang的递归用法来实现排列，比循环方法要简洁很多：

Haskell:

java 代码

permutation [] = [[]]
permutation xs = [x:ys | x <- xs, ys <- permutation (delete x xs)]

Erlang:

java 代码

permutation([]) -> [[]];
permutation(L)  -> [[H|T] || H <- L, T <- permutation(L--[H])].

应用举例：

AlbertLee出的一道面试题： http://www.douban.com/group/topic/1237059/
用1、2、2、3、4、5这六个数字（注意有两个2）， 打印出所有不同的排列，如：512234、412325等，要求："4"不能在第三位，"3"与"5"不能相连。

我稍微改了一下的Haskell解法如下：

java 代码

module Main where
import List

inlist [] [] = True
inlist a [] = False
inlist a [x] = False
inlist a (x:nx) = (a == [x, head nx] || a == [head nx, x]) || inlist a nx
notinlist a b = not (inlist a b)  --不相连判断

permutation [] = [[]]
permutation xs = [x:ys | x <- xs, ys <- permutation (delete x xs)]  --排列

third list = list!!2 /= 4  --第三位判断，这个硬编码啦

s = [1,2,2,3,4,5]
res2 = filter (notinlist [3,5]) $ filter third $ nub $ permutation s
main = print (length res2)

更新：

Erlang在语法上和Haskell有不少类似如list comprehension，pattern match和immutable data，语意上则要简单很多，没有太多新概念比如lazy evaluation:

java 代码

fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

这个使用递归的list comprehension来计算fibonacci数的方法Erlang是没法照搬的，因为fibs是个无限list。

更新2:

新版F#终于也增加了list comprehension，这样在F#可以写成：

java 代码

let delete item list = List.filter (fun x -> x <> item) list

let rec permutation x = match x with
  |[] -> [[]]
  |xs -> [for x in xs for y in permutation (delete x xs) -> x::ys]

评论

5 楼 cookoo 2007-01-16  

随机数每次输出都会不同，实际上内部依赖于某种状态也就是有side effect，需要用monad封装：

import List
import Random

randomPerm :: [a] -> StdGen -> [a] 
randomPerm list gen = map (list!!) rl 
  where l = length list
        rl =  take l $ nub $ randomRs (0,l - 1) gen

randomPermIO :: [a] -> IO [a]
randomPermIO list = do
  g <- newStdGen
  return $ randomPerm list g  

randomPerm是个pure的函数，结果完全依赖参数。randomPermIO每次产生一个新的随机数产生器，供randomPerm使用。

4 楼 快乐的小猪 2007-01-14  

您好，看了你写的东西很受启发，我是初学者，正为Haskell的很多问题而困扰着.比如 这个 IO 怎么理解呐?  对于这个问题, 如您上面讲的Permutation排列问题,如果用随机的(Random)方法该怎样实现?看了不少资料,就是似懂非懂. 晕啊. 

函数是这样表示:

RandomPermt :: Ord a=> [a]-> IO[a]

3 楼 T55555 2007-01-08  

Have a look at ...
http://davidtran.doublegifts.com/blog/?p=5

module Main where
import Data.List

permutations [] = [[]]
permutations xs = [x:ps | x <- nub xs, ps <- permutations (delete x xs)]

digits = [1,2,2,3,4,5]

check xs =
  xs !! 2 /= 4  &&
  abs (p3 - p5) /= 1
  where
    Just p3 = elemIndex 3 xs
    Just p5 = elemIndex 5 xs

result = filter check (permutations digits)

main = do
--  print result
    print (length result)

2 楼 zhangyu8374 2006-12-01  

comprehension确实挺狠的。

看看这个，也是comprehension的体现，太自然了！
my_concat :: [[a]]->[a]
my_concat xss = [x|xs<-xss,x<-xs]

1 楼 dogstar 2006-11-26  

很羡慕你可以由着性子去学习，特别是能容易买到原版的书。哈哈。