Haskell 树结构

Question

需要一些帮助来编写一个 Haskell 函数，该函数接受一个字符串并创建一个二叉树。需要有更好 Haskell 经验的人的帮助来为我填补一些漏洞并描述原因，因为这对我来说是一次学习经历。

我在 Haskell（示例 **B**DECA）中的一个项目中得到了一棵用单个字符串编码的树。星号表示一个节点，任何其他字符表示一个叶子。我正在尝试用从输入中读取的信息填充此数据结构。

data Trie = Leaf Char | Branch Trie Trie

我更喜欢数学和命令式编程，所以我发现我可以通过从左到右解析来定义子树。一棵合适的树将比 * 多 1 个字符。数学上我会想到一个递归结构。

如果第一个字符不是 *，则解决方案是第一个字符。否则解决方案是一个分支，其中子分支被反馈到函数中，其中左分支是第一组字符，其中字符数 *，右分支是其他所有字符。

constructTrie :: String -> Trie
constructTrie x = if x !! 1 == '*' then
                      let leftSubtree = (first time in drop 1 x where characters out number *'s)
                          rightSubtree = (rest of the characters in the drop 1 x)
                      in Branch constructTrie(leftSubtree) constructTrie(rightSubtree)
                  else Leaf x !! 1

主要是我需要帮助定义左右子树，如果这样定义有什么问题。

Answer 1

!!（顺便说一下，它是 0 索引的）通常是不行的。这是一件非常 "imperative" 的事情，而且像这里这样的常量索引特别难闻。这意味着你真的想要一个模式匹配。此外，在索引处拆分列表 (type String = [Char]) 并分别对两部分进行操作是一个坏主意，因为这些列表是链接的且不可变的，因此您最终将复制整个第一部分。

您想要执行此操作的方式如下：

如果字符串为空，则失败。
如果它以 * 开头，则执行某种操作，以某种方式解析左子树并一步获取列表的剩余部分，然后从剩余部分中解析出右边的子树，从而生成 Branch.
如果是另一个字符，则制作一个Leaf。

不需要弄清楚在哪里拆分字符串，实际拆分字符串，然后解析两半；只是解析列表，直到你不能再解析，然后剩下的（或者我应该说正确？）可以再次解析。

因此：定义一个函数 constructTrie' :: String -> Maybe (Trie, String)，它将 String 的开始消耗到 Trie，然后留下未解析的位（并给出 Nothing 如果它只是无法解析）。这个函数将是递归的，这就是它获得额外输出值的原因：它需要额外的管道来移动列表的其余部分。 constructTrie 本身可以定义为它的包装器：

-- Maybe Trie because it's perfectly possible that the String just won't parse
constructTrie :: String -> Maybe Trie
constructTrie s = do (t, "") <- constructTrie' s
                  -- patmat failure in a monad calls fail; fail @Maybe _ = Nothing
                     return t

-- can make this local to constructTrie in a where clause
-- or leave it exposed in case it's useful
constructTrie' :: String -> Maybe (Trie, String)
constructTrie' "" = Nothing -- can't parse something from nothing!
constructTrie' ('*':leaves) = do (ln, rs) <- constructTrie' leaves
                              -- Parse out left branch and leave the right part
                              -- untouched. Doesn't copy the left half
                                 (rn, rest) <- constructTrie' rs
                              -- Parse out the right branch. Since, when parsing
                              -- "**ABC", the recursion will end up with
                              -- constructTrie' "*ABC", we should allow the slop.
                                 return (Branch ln rn, rest)
constructTrie' (x:xs) = return (Leaf x, xs)

这是一个非常常见的模式：定义一个带有额外管道的递归函数来传递一些状态并将它包装在一个更好的状态中。我想这对应于命令式循环通常如何改变变量以保持其状态。

Haskell 树结构

Haskell Tree construction

string

tree

haskell

huffman-code