递归遍历目录之Haskell, Java, Clojure对比

递归的遍历一个目录, 列出其中所有的文件是一个常见的操作. 我们可以比较一下分别在Haskell, Java, Clojure当中怎么实现这个任务. 首先是Haskell, 这个例子来源于Real World Haskell

 
import Data.Char
import Control.Monad
import System.Directory
import System.FilePath
 
getRecursiveContents :: FilePath -> IO [FilePath]
getRecursiveContents topdir = do
  names <- getDirectoryContents topdir
  let properNames = filter (`notElem` [".", ".."]) names
  paths <- forM properNames $ \name -> do
    let path = topdir </> name
    isDirectory <- doesDirectoryExist path
    if isDirectory
      then getRecursiveContents path
      else return [path]
  return (concat paths)
 

Haskell的特点非常鲜明, 首先是IO和纯函数是严格分开的. 所有IO操作产生的值都包含在monad当中, 这个函数本身也是返回IO action. 从IO monad中拿出值用的是pull out 操作符.

 
<-
 

这种写法是编译器强制的, 无法写成如下的样子

 
  let properNames = filter (`notElem` [".", ".."]) (getDirectoryContents topdir)
 

如果这样写的话, 会导致什么结果? 因为getDirectoryContents是和外部世界打交道的, 那么对于同样的参数他会返回不同的值, 例如从某个目录中删除了文件, 然后导致filter函数也变为非纯函数, 同样任何使用filter结果的函数也不是pure的. 有副作用的函数会感染所有调用他的函数.

所以这种写法看起来比较冗余, 但是对于Haskell而言则是必须的.

这里return和普通的命令式语言中的return相似, 不过return的任何值都会包裹到monad当中, 这里是IO monad. 如果for loop的匿名函数返回monad, 那么应该使用forM, 这是专门为产生副作用的loop而设置的for循环. 这里forM的返回类型是IO [[FilePath]], paths的类型是[[FielPath]], getRecursiveContent的类型是IO [FilePath].

如果我们希望返回的结果当中也包含目录的话, 可以这样写

 
getRecursiveContentsIncludeDir ::   FilePath -> IO [FilePath]
getRecursiveContentsIncludeDir topdir = do
  names <- getDirectoryContents topdir
  let properNames = filter (`notElem` [".", ".."]) names
  paths <- forM properNames $ \name -> do
    let path = topdir </> name
    isDirectory <- doesDirectoryExist path
    if isDirectory
      then do
        subdirs <- (getRecursiveContentsIncludeDir path)
        return ([path ++ " [DIR]"] ++ subdirs) 
      else return [path]
  return (concat paths)
 

思路是在递归调用产生的结果当中加入他们当前目录.

如果要对后缀名进行过滤

 
toLowerCase str = Prelude.map Data.Char.toLower str
hasSuffix name suffix = (toLowerCase suffix) == (toLowerCase $ snd $ splitExtension name)
 
getRecursiveContentsIncludeDirWithSuffix :: FilePath -> String  -> IO [FilePath]
getRecursiveContentsIncludeDirWithSuffix topdir suffix = do
  names <- getDirectoryContents topdir
  let properNames = filter (`notElem` [".", ".."]) names
  paths <- forM properNames $ \name -> do
    let path = topdir </> name
    isDirectory <- doesDirectoryExist path
    if isDirectory
      then do
        subdirs <- (getRecursiveContentsIncludeDirWithSuffix path suffix)
        return ([path ++ " [DIR]"] ++ subdirs) 
      else if hasSuffix name suffix
        then return [path]
        else return []
  return (concat paths)
 
 

再来看Java的实现, 和Haskell一样都静态类型的, 上面Haskell的代码中除了函数本身指定了类型, 大部分代码都没有直接标明类型, 因为Haskell的类型系统可以自动推断类型. Java这样的语言的类型系统就要逊色许多, 几乎没有什么智能. 需要为一切使用到的东西指定类型.

 
    public static List<String> listRecursively(String dir) {
        File f = new File(dir);
        List<String> ret = new ArrayList<String>();
 
        if( ! f.isDirectory()) {
            return ret; // return empty list
        }
 
        File [] fileList = f.listFiles();
        for( File file : fileList) {
            if( file.isDirectory()) {
                ret.addAll (listRecursively(dir + "\\" + file.getName()));
            } else {
                ret.add(dir + "\\" + file.getName());
            }
        }
        return ret;
    }
 

最后是Clojure, Clojure与Haskell类似是函数式语言, 但是是动态类型的. 第一个版本是复制上面的思路

 
(defn list-recursively [dir]
  (let [f (java.io.File. dir)]
    (if (.isDirectory f)
      ;then
      (let [fileList (.listFiles f)]
        (apply concat (for [file fileList]
          (let [path (str dir "\\" (.getName file))]
            (if (.isDirectory file)
              ;then
              (concat [] (list-recursively path))
              ;else
              [path]
            )
          )
        ))
      )
      ;else
      []
    )
  )
)
 

如果是对LISP或者函数式不太熟悉的人, 可能会看的莫名其妙. 只看见成堆的括号和一些单词无规律的排列在一起, 不知道哪里是赋值, 哪里是返回.唯一在视觉上有点用处的可能就是缩进了.

其实思路是一样的. f (java.io.File. dir) 等于 File f = new File(dir), Clojure 中叫做绑定不叫赋值. 这里for的返回类型是'([string]), 即string vector 的list. 因为for的每次循环产生的是[string]类型. 那么(apply concat for)的类就是[string], 从而推断整个函数的类型就是[string].

下面是更加函数式的写法, 消除了for循环.

 
(defn list-recursively [dir]
  (let [f (java.io.File. dir)]
    (if (.isDirectory f)
      ;then
      (let [fileList (.listFiles f)
            dirs (filter #(.isDirectory %) fileList)
            files (filter #(not (.isDirectory  %)) fileList)
           ]
        (apply concat (concat (map #(concat [] (list-recursively (str dir "\\" (.getName %)) )) dirs)
                              (map #(vec [ (str dir "\\" (.getName %))]) files)))
      )
      ;else
      []
    )
  )
)
 

动态类型既是优点也是缺点, 优点是写起来快, 但是读起来就会很麻烦. 同时这个特点也鼓励了基于REPL的编码模式, 即写一点代码就立即在REPL中验证其正确性, OK之后, 继续写剩下的代码. 而Haskell, Java的代码基本可以通过阅读源码验证其正确性, 即使没有看到的, 编译器也能提示. 而Haskell基本可以在编译阶段消除大部分的错误, 运行的时候往往是一次成功.