haskell - 使用(伪)可变 Map 调用函数(并更改 Map)

Question

我玩过 Haskell，但只是玩玩而已。使用真正的不变性让我感到困惑。
具体来说，我有以下功能(现在主要是调试我投入的东西。

type BySize = Map Int [Finfo]
-- ... other stuff ...
-- Walk directories and return map
walkDir :: String -> BySize -> IO ([BySize])
walkDir rootdir bySize = do
    let !bySizeHist = [bySize]
    pathWalk rootdir (\root dirs files -> do
        forM_ files $ (\file -> do
            let !latest = head bySizeHist
            finfo <- do processPath (joinPath [root, file]) latest
            let !new = addBySize (f_size finfo) finfo latest

            let latest_size = Map.keys latest
            let new_size = Map.keys new
            let error = if latest == new
                then
                    "Error, identical maps!"
                else
                    "Update of map is fine" ++ (show latest_size) ++ (show new_size)
            putStrLn error

            let !bySizeHist = [new] ++ bySizeHist
            putStrLn (fname finfo) ))
    return bySizeHist

基本上，我的目标是获得一个 Map具有 key 文件大小和 Finfo 列表(文件信息) data结构作为值。我尝试了很多不同的变体，这只是最新的一个不起作用。
我知道 Maps 是不可变的，所以我希望生成一个版本列表，然后在下游使用最新的版本。但我想也许我应该使用 State monad 来代替。我实际上并不关心 Map 版本的历史，我只是以一种摸索的方式尝试它。
函数 addBySize自己工作。也就是说，给定大小和一个新的 Finfo 对象，它会根据旧的 Map 正确返回一个新的 Map，但是添加了一个新的键，或者现有的键映射到的列表用新的 Finfo 对象扩展。
问题是试图“重新绑定(bind)” bySizeHist失败(我认为是因为超出了循环范围)。因此，虽然我想在每次循环过程中不断回显扩展的键列表，但我得到的是:

% haskell/find-dups haskell
Update of map is fine[][6]
/home/dmertz/git/LanguagePractice/haskell/that
Update of map is fine[][3235]
/home/dmertz/git/LanguagePractice/haskell/sha1sum.hi
Update of map is fine[][8160]
/home/dmertz/git/LanguagePractice/haskell/sha1sum.o
Update of map is fine[][241]
/home/dmertz/git/LanguagePractice/haskell/sha1sum.hs
Update of map is fine[][6]

IE。 latest从来都不是 map 的最新版本，但我总是添加 new在每个循环上，但总是到空的 BySize Map。
下面提出的解决方案非常有用。但是，我希望排除符号链接(symbolic link)。
我修改了 getAllFiles在某种程度上，试图排除符号链接(symbolic link)。但我的方法未能排除作为符号链接(symbolic link)的目录。我尝试了一些不起作用的变体。我的版本仅部分有效:

-- Lazily return (normal) files from rootdir
getAllFiles :: FilePath -> IO [FilePath]
getAllFiles root = do
  nodes <- pathWalkLazy root
  -- get file paths from each node
  let files = [dir </> f | (dir, _, files) <- nodes, f <- files ]
  normalFiles <- filterM (liftM not . pathIsSymbolicLink) files
  return normalFiles

Answer 1

我会让其他人直接回答您的问题，但正确的做法可能是不这样做。你要写的程序是:

getBySize :: FilePath -> IO BySize
getBySize root = do
  -- first, get all the files
  files <- getAllFiles root
  -- convert them all to finfos
  finfos <- mapM getFinfo files
  -- get a list of size/finfo pairs
  let pairs = [(f_size finfo, finfo) | finfo <- finfos]
  -- convert it to a map, allowing duplicate keys
  return $ fromListWithDuplicates pairs

这是实现目标的合理且实用的方式。您一次获取所有文件名并应用一些功能转换(到 Finfos、成对、到 map )。无需为可变性或状态大惊小怪。
写作 fromListWithDuplicates有点复杂，但它是标准的。它经常被重写，以至于它或类似的东西应该是 Data.Map 的一部分。 :

fromListWithDuplicates :: Ord k => [(k, v)] -> Map k [v]
fromListWithDuplicates pairs = Map.fromListWith (++) [(k, [v]) | (k, v) <- pairs]

这个想法是它采用键值对列表，将所有值转换为单例列表，然后使用 fromListWith在重复的情况下，通过将这些单例连接在一起来生成映射。
您可能已经有了 getFinfo功能，无论您的 Finfo是。我使用以下内容进行测试:

data Finfo = Finfo { f_path :: FilePath, f_size :: Int }

getFinfo :: FilePath -> IO Finfo
getFinfo path = do
  sz <- getFileSize path
  return $ Finfo path (fromIntegral sz)

唯一剩下的功能是 getAllFiles ，它获取所有文件的列表(作为完整路径名，已经加入父目录)。一种写法是使用 pathWalkLazy来自 System.Directory.PathWalk :

getAllFiles :: FilePath -> IO [FilePath]
getAllFiles root = do
  nodes <- pathWalkLazy root
  -- get file paths from each node
  let files = [dir </> file | (dir, _, files) <- nodes, file <- files]
  return files

一个完整的示例程序。它需要一个参数，即要处理的目录。

import System.Directory
import System.Directory.PathWalk
import System.Environment
import System.FilePath
import Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map

type BySize = Map Int [Finfo]

getBySize :: FilePath -> IO BySize
getBySize root = do
  -- first, get all the files
  files <- getAllFiles root
  -- convert them all to finfos
  finfos <- mapM getFinfo files
  -- get a list of size/finfo pairs
  let pairs = [(f_size finfo, finfo) | finfo <- finfos]
  -- convert it to a map, allowing duplicate keys
  return $ fromListWithDuplicates pairs

-- this is a little complicated, but standard
fromListWithDuplicates :: Ord k => [(k, v)] -> Map k [v]
fromListWithDuplicates pairs = Map.fromListWith (++) [(k, [v]) | (k, v) <- pairs]

getAllFiles :: FilePath -> IO [FilePath]
getAllFiles root = do
  nodes <- pathWalkLazy root
  -- get file paths from each node
  let files = [dir </> file | (dir, _, files) <- nodes, file <- files]
  return files

data Finfo = Finfo { f_path :: FilePath, f_size :: Int }
  deriving (Show)

getFinfo :: FilePath -> IO Finfo
getFinfo path = do
  sz <- getFileSize path
  return $ Finfo path (fromIntegral sz)

main = do
  [root] <- getArgs
  bs <- getBySize root
  print bs