如何在Haskell中的类似文件系统的结构中进行搜索

Question

问题

我有类型：

data FSObject = Folder String [FSObject] | File String

并且我需要做一个函数

search :: String -> FSObject -> Maybe String

返回我们正在搜索的文件的路径（如果存在）（搜索功能中的字符串应等于搜索到的文件的名称（文件对象中的字符串（不带路径））。

我的想法/尝试

我觉得我在功能上做得不好。我是该语言的新手，因此对以下代码感到抱歉。

我尝试这样做了几个小时。我正在尝试这样：

heler函数包含，如果给定的FSObject包含我们正在寻找的文件，则返回true

返回带有文件的第一个元素的帮助器功能（使用先前的功能和“查找”功能）

帮助程序处理从Maybe String到String的转换

我的搜索功能将检查是否存在文件，如果否，则返回Nothing，否则返回Just with with String通过递归计算得出

我可以粘贴我的作品，但是我不知道如何使它起作用，它完全不可读，等等。

some1是否有要分享的提示/意见？如何正确处理Maybe这类问题？

Answer 1

您可以使用递归来完成。

findPath::String->FSObject->Maybe String
findPath name (File name') | name == name' = Just name
findPath _ (File _) = Nothing
findPath name (Folder path contents) = 
             fmap ((path ++ "/") ++) $ msum $ map (findPath name) contents 

唯一棘手的地方是最后一部分。将最后一行分开。...

map (findPath name) contents

将输出子结果列表

[Just "a/b/filename", Nothing, Just "c/d/filename", ....]

[msum将获得列表中的第一个Just，将其余的扔掉（而且，由于懒惰，实际上不会创建第一个值）]

最后，路径是前置的（fmap在此到达Maybe内部）

Answer 2

虽然@jamshidh解决方案很短，但它不是模块化的，并且是最终结果。这是我编写程序的过程。两个要点：

• 我将使用所谓的“先生成然后搜索”方法：首先为所有文件生成路径，然后在集合中搜索正确的路径
• 我将路径存储为组件列表-这样，代码将更通用（在Haskell中，更通用的代码不易出错），然后我将在一个小函数中插入路径分隔符（因此我可以做一件事在更容易的时间）。

好的，我需要allPaths函数，该函数可以为我提供所有文件及其路径的列表。单个文件的所有路径就是该单个文件，并且文件夹的所有路径都是从子级开始的，具有前缀文件夹名称的子级路径的集合：

allPaths (File file) = singleFile file
allPaths (Folder folder children) = concatMap (addFolder folder . allPaths) children

我实际上是自上而下编写代码的。因此，我此时无需定义singleFile和addFolder。单个文件很简单：

singleFile file = [(file, [])]

addFolder将f添加到元组的第二个分量。 Control.Arrow中已经有一个函数，但是为了简单起见，我在这里添加了它的实现：

second f (a,x) = (a, f x)

addFolder f files = map (second (f:)) files

[当我学习Haskell时，很难立即编写这样的代码，但是现在它是自动的，没有中间步骤。

现在，我们基本上通过过滤所有匹配文件，获取第一个匹配并提取路径来实现search。哦，标准库中已经有相应的函数lookup：

search fileToSearch l = lookup fileToSearch $ allPaths l

[花了我很长时间才弄清楚如何编写lookup和allPaths。幸运的是，偶然地正确选择了元组中的顺序。

注意，您仍然需要通过使用concatMap插入分隔符并在必要时附加文件名来将文件夹列表转换为路径。

Answer 3

您应该使用一个累加参数创建一个递归函数，以将当前路径保存在搜索中。就像这样：

    search str (File f) = if str == f then Just str else Nothing
    search str (Directory dir (x:xs)) = 
       Just (sear str [] (Directory dir (x:xs))) where
            sear str path (File f) = if str == f then (path ++ "/" ++ str ++ "|") else []
            sear str path (Directory y []) = []
            sear str path (Directory dir (x:xs)) = sear str (path ++ "/" ++ dir) x ++ sear str path (Directory dir xs)

希望对您有帮助。