当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

List comprehension和递归的巧妙结合

发表于: 2006-11-18   作者:cookoo   来源:转载   浏览:
摘要: 我以前总以为list comprehension这个语法糖不过就是些map,filter转换罢了,最近看到Haskell和Erlang的递归用法来实现排列,比循环方法要简洁很多: Haskell: java 代码 permutation [] = [[]]      permutation
我以前总以为list comprehension这个语法糖不过就是些map,filter转换罢了,最近看到Haskell和Erlang的递归用法来实现排列,比循环方法要简洁很多:

Haskell:
java 代码
  1. permutation [] = [[]]     
  2. permutation xs = [x:ys | x <- xs, ys <- permutation (delete x xs)]  

Erlang:
java 代码
  1. permutation([]) -> [[]];  
  2. 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 代码
 
  1. module Main where   
  2. import List   
  3.    
  4. inlist [] [] = True   
  5. inlist a [] = False   
  6. inlist a [x] = False   
  7. inlist a (x:nx) = (a == [x, head nx] || a == [head nx, x]) || inlist a nx   
  8. notinlist a b = not (inlist a b)  --不相连判断 
  9.    
  10. permutation [] = [[]]   
  11. permutation xs = [x:ys | x <- xs, ys <- permutation (delete x xs)]  --排列 
  12.    
  13. third list = list!!2 /= 4  --第三位判断,这个硬编码啦 
  14.    
  15. s = [1,2,2,3,4,5]   
  16. res2 = filter (notinlist [3,5]) $ filter third $ nub $ permutation s     
  17. main = print (length res2)  


更新

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

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

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

更新2:

新版F#终于也增加了list comprehension,这样在F#可以写成:
java 代码
 
  1. let delete item list = List.filter (fun x -> x <> item) list  
  2.   
  3. let rec permutation x = match x with  
  4.   |[] -> [[]]  
  5.   |xs -> [for x in xs for y in permutation (delete x xs) -> x::ys]  



List comprehension和递归的巧妙结合

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号