Haskell中两棵树的并集

dced5bon 于 2022-11-14 发布在其他

关注(0)|答案(1)|浏览(150)

我正在努力在haskell中对这个问题的域进行建模。
我知道如何用过程语言解决这个问题（用循环，这相当容易），但似乎不知道如何用Haskell来解决这个问题。
我想合并（联合）RoseDirTree。

data RoseDirTree
      = File Text Int
      | Folder Text [RoseDirTree]
      deriving (Show, Eq, Ord)

-- | Merges two dir trees
-- If file names are same, prefers the right hands side.
mergeDirTree :: RoseDirTree -> RoseDirTree -> RoseDirTree
mergeDirTree = undefined

下面是一个示例案例：

archivesFromS3 :: RoseDirTree
archivesFromS3 = Folder "/"
      [ Folder "2011"
            [ File "jan.dump" 0
            , File "feb.dump" 0
            ]
      , Folder "2012"
            [ File "jan.dump" 0
            ]
      ]

archivesFromLocal :: RoseDirTree
archivesFromLocal = Folder "/"
      [ Folder "2011"
            [ File "jan.dump" 1
            , File "march.dump" 1
            ]
      , Folder "2019"
            [ File "jan.dump" 1
            ]
      ]

-- | archivesFromS3 `mergeDirTree` archivesFromLocal
expectedMerged :: RoseDirTree
expectedMerged = Folder "/"
      [ Folder "2011"
            [ File "jan.dump" 1
            , File "feb.dump" 0
            , File "march.dump" 1
            ]
      , Folder "2012"
            [ File "jan.dump" 0
            ]
      , Folder "2019"
            [ File "jan.dump" 1]
      ]

从更多的树问题Angular 来看，我最初的想法是结构必须采用以下形式：

mergeTree :: RoseDirTree -> RoseDirTree -> RoseDirTree
mergeTree (File lhsName idl) (File rhsName idr) = 
      if lhsName == rhsName 
      then File rhsName idr 
      else error "can't merge two different file"
mergeTree (Folder lhsName childl) (Folder rhsName childr) = 
      if lhsName == rhsName 
      then Folder rhsName (childl <> childr) 
      else error "can't merge two different folder"
mergeTree _ _ = error "cannot merge file and folder"

但很显然，这种方法：
1.不处理文件夹具有同名嵌套文件夹的情况。
我真的不知道下一步该去哪里。任何建议都很感谢。

haskell

来源：https://stackoverflow.com/questions/73025941/union-of-two-trees-in-haskell

1条答案

按热度按时间

wfveoks01#

有问题的部分是childl <> childr。请改为定义新函数：

mergeChildren :: [RoseDirTree] -> [RoseDirTree] -> [RoseDirTree]
mergeChildren = undefined

此函数应在某个时刻调用mergeTree函数。
需要考虑的一点是，你是否可以假设输入的文件和文件夹名称是排序的。如果它们是排序的，你就可以用一种稍微简单一点的方式来实现它。如果你被允许使用Data.List.sortOn函数，你也可以考虑自己对它们进行排序。
如果输入被排序，则该函数在结构上可以类似于合并排序的合并，例如this one by Redu：

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys         = ys
merge xs []         = xs
merge (x:xs) (y:ys) | x < y     = x:merge xs (y:ys)
                    | otherwise = y:merge (x:xs) ys

不同之处在于，您需要不同的比较函数，并且如果文件夹或文件相等，则需要执行不同的操作。

剧透

假设输入是排序的，下面是我如何实现mergeChildren函数，这仍然需要实现一个自定义的比较函数。

-- | Compares the names of the top level file or folder
-- Returns LT if the first input is a file and the second a folder
-- Returns GT if the first input is a folder and the second a file 
compareTree :: RoseDirTree -> RoseDirTree -> Ordering
compareTree = undefined

mergeChildren :: [RoseDirTree] -> [RoseDirTree] -> [RoseDirTree]
mergeChildren [] ys         = ys
mergeChildren xs []         = xs
mergeChildren (x:xs) (y:ys) = 
  case compareTree x y of
    LT -> x             : mergeChildren xs (y:ys)
    EQ -> mergeTree x y : mergeChildren xs ys
    GT -> y             : mergeChildren (x:xs) ys

赞(0）回复(0）举报 2022-11-14

我来回答

Haskell中两棵树的并集

1条答案

剧透

相关问题

热门标签

最新问答