Haskell二叉树递归

Question

我是haskell的初学者，我需要根据列表(路径)中指定的方向在树中显示值。我在下面列出了数据结构，我想了解为什么我实现的递归功能是错误的

import Data.List
 data Step = L | R
 deriving(Eq,Show)
type Path = [Step]  
 data Tree a = Node a (Tree a) (Tree a)
             | End
        deriving (Eq,Show)
      leaf :: a -> Tree a
      leaf x = Node x End End
     ex :: Tree Int

     ex = Node 4 (Node 3 (leaf 2) End)
               (Node 7 (Node 5 End (leaf 6))
                     (leaf 8))

        valueAt :: Path -> Tree a -> Maybe a
        valueAt (p:ps) (Node a l r)  
                               | p == L = valueAt ps l 
                               | p == R = valueAt ps r
                               | ps == [] = Just           
                               | otherwise = Nothing

//当我执行这个时，它说非穷举函数在valueAt。所以我猜我的递归思想实现错了。有谁能解释一下吗?

Answer 1

您没有处理valueAt [] someTree。行valueAt (p:ps) ...只匹配从p开始到ps的非空列表。ps可能是空的，但p:ps永远不是。

如果你使用-Wall标志进行编译，GHC应该在编译时发出警告。我强烈推荐这个。

作为一个样式建议，避免像p == ...这样的守卫，因为它们不执行任何模式匹配。不如试试

valueAt :: Path -> Tree a -> Maybe a
valueAt []     (Node a _ _) = Just a    -- note the "a" !
valueAt (L:ps) (Node _ l _) = valueAt ps l
valueAt (R:ps) (Node _ _ r) = valueAt ps r
valueAt _      End          = Nothing   -- in all the other cases

Answer 2

valueAt的模式匹配不包括[]，因为(p:ps)将在空列表上失败。然而，它没有必要这样做。守卫是按照它们被写入的顺序求值的，这意味着你的p == L和p == R守卫是在你的ps == []情况之前求值的。换句话说，您将边缘情况放在递归情况之后，从而导致无效的模式匹配。下面的代码应该可以解决这个问题。

valueAt (p:ps) (Node a l r)  
                           | ps == [] = Just    
                           | p == L = valueAt ps l 
                           | p == R = valueAt ps r       
                           | otherwise = Nothing

然而，你的代码有另一个问题。该函数具有类型描述valueAt :: Path -> Tree a -> Maybe a，但在您的边缘情况(ps == [])中，Just具有类型a -> Maybe a;Just应用于太少的参数。

                           | ps == [] = Just a

既然你的错误被修复了，我还建议从守卫和==转移到模式匹配。它将更简单、更快、更少出错。

valueAt :: Path -> Tree a -> Maybe a
valueAt []     (Node a _ _) = Just a
valueAt (L:ps) (Node _ l _) = valueAt ps l
valueAt (R:ps) (Node _ _ r) = valueAt ps r
valueAt _      _            = Nothing