Haskell树结构 [英] Haskell Tree construction

问题描述

需要一些帮助来编写一个Haskell函数，该函数需要一个字符串并创建一个二叉树.需要具有更好Haskell经验的人一些帮助，以填补我的一些空白并描述原因，因为这对我来说是学习的经验.

Need some help writing a Haskell function that takes a string and creates a binary tree. Need some help from someone with a little better Haskell experience to fill in some holes for me and describe why because this is a learning experience for me.

为Haskell中的项目提供了一个用单个字符串编码的树(示例 ** B ** DECA ).星号表示节点，其他任何字符表示叶子.我正在尝试使用从输入中读取的信息来填充此数据结构.

I'm given a tree encoded in a single string for a project in Haskell (Example **B**DECA). The star denotes a node any other character denotes a Leaf. I'm trying to fill this data structure with the information read in from input.

数据Trie = Leaf Char |分支Trie Trie

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

I'm more of a math and imperative programming guy so I made the observation that I can define a subtree by parsing from left to right. A proper tree will have 1 more character than *. Mathematically I would think of a recursive structure.

如果第一个字符不是 * ，则解决方案为第一个字符.其他解决方案是一个分支，其中子分支被反馈到函数中，其中左分支是第一个字符集，其中字符输出编号为 * ，而右分支为其他所有字符.

If the first character is not a * the solution is the first character. Else the solution is a Branch where the subbranches are feed back into the function where the left Branch is the first set of characters where Characters out number *'s and the right Branch is everything else.

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

大多数情况下，我需要定义左和右子树的帮助，以及如果用这种方法定义有任何问题.

Mostly I need help defining the left and right subtree and if there is anything wrong with defining it this way.

推荐答案

!! (顺便说一下，它是 0 索引的)通常是-去.这是一件非常当务之急"的事情，对于像这样的常量索引，它尤其臭.那意味着你真的想要一个模式匹配.另外，在索引处拆分列表( type String = [Char] )并分别在两个部分上操作也是一个坏主意，因为这些列表是链接的并且是不可变的，因此最终将导致复制整个第一部分.

!! (which, by the way, is 0-indexed) is usually a no-go. It's a very "imperative" thing to do, and it's especially smelly with constant indices like here. That means you really want a pattern match. Also, splitting a list (type String = [Char]) at an index and operating on the two parts separately is a bad idea, because these lists are linked and immutable, so you'll end up copying the entire first part.

您要执行的操作如下:

• 如果字符串为空，则失败.
• 如果它以 * 开头，则执行某种方式解析左侧子树并一步获得列表的其余部分，然后解析其余部分中的右侧子树，分支.
• 如果是其他字符，请制作 Leaf .

• If the string is empty, fail.
• If it starts with a *, then do something that somehow parses the left subtree and gets the remainder of the list in one step, and then parse the right one out of that remainder, making a Branch.
• If it's another character, make a Leaf.

没有必要弄清楚在哪里分割字符串，实际上是分割字符串，然后解析两半；只是解析列表，直到无法解析为止，然后可以再次解析剩下的内容(或者我应该说对了吗?).

There's no need to figure out where to split the string, actually split the string, and then parse the halves; just parse the list until you can't anymore and then whatever's left (or should I say right?) can be parsed again.

因此:定义一个函数 constructTrie':: String->也许(Trie，String)会将 String 的开头消耗为 Trie ，然后将未解析的位留在后面(并给出 Nothing (如果它只是无法解析).该函数将是递归的，这就是为什么它获得了额外的输出值的原因:它需要额外的管道来移动列表的其余部分.然后可以将 constructTrie 本身定义为其周围的包装器:

So: define a function constructTrie' :: String -> Maybe (Trie, String) that consumes the start of a String into a Trie, and then leaves the unparsed bit behind (and gives Nothing if it just fails to parse). This function will be recursive, which is why it gets that extra output value: it needs extra plumbing to move the remainder of the list around. constructTrie itself can then be defined as a wrapper around it:

-- 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)

这是一种非常常见的模式:使用额外的管道定义递归函数以传递某些状态并将其包装为更好的状态.我想这与命令式循环通常如何变异变量以保持其状态相对应.

This is a very common pattern: defining a recursive function with extra plumbing to pass around some state and wrapping it in a nicer one. I guess it corresponds to how imperative loops usually mutate variables to keep their state.

这篇关于Haskell树结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！