Haskell中的叶子树 - 非穷举模式 [英] Leaf Trees in Haskell - non-exhaustive pattern

问题描述

 数据LTree a =>这个函数遵循Bools的路径，向左或向右依赖于False或True，留下
 |叉（LTree a）（LTree a）
派生（显示）
 
 select :: LTree a  - > [Bool]  - > （可能是a）
 select（Fork（Leaf a）（Leaf b））（l：ls）= if l == False then a 
 else b 
 select（Fork lr） （b：bs）= if b == False然后选择l bs 
其他选择r bs 
  

< LTree没有声明空值，我怎么能知道它是一个节点或一个叉，我陷入我的函数？

解决方案

询问编译器

GHC可以在编译时警告您非穷举的模式，而不是等待运行时间来发现它们。如果我把你的代码放到一个文件中并用 -fwarn-incomplete-patterns flag

  ghc -fwarn-incomplete-patterns nonExhaustiveLeafTree.hs 
  

它会产生以下错误消息：

 模式匹配非穷举
在`select'等式中：
模式不匹配：
（Leaf _）_ 
（Fork（_ _）_）[] 
（Fork（Leaf _）（Fork _ _））[] 
（ Fork（Leaf _）（Leaf _））[] 
  

在添加规则，你在你的回答中建议覆盖 [] ，它仍会产生一个警告，树是 Leaf _

 模式匹配非穷举
在`select'的等式中：模式不匹配：（Leaf _）_ 
  

涵盖所有内容

如果我们处理 Leaf s和<$ c，我们可以很容易地覆盖所有模式$ c> Fork s彼此分开。这也删除了当直接后代是叶子时决定 Fork 的去路的重复代码。

当您到达 Leaf 时，您会知道有一个结果，并且没有可供遵循的路径。

  select（Leaf a）[] =只要
  

当您到达 Leaf 时，您需要决定做什么，并且仍然需要遵循一条路径。

  select（Leaf a）（l：ls）= ???? 
  

就像你在你的回答中提到的那样，当没有路径离开时，你会知道没有结果 Fork 。

  select（Fork _ _）[] = Nothing 
  

您可以简化分叉和单个规则路径时发生的情况。

  select（Fork lr）（b：bs）= if b 
然后选择r bs 
 else else l bs 
  

This function follows a path of Bools, going left or right depending on False or True, respectively

data LTree a = Leaf a 
             | Fork (LTree a) (LTree a)
             deriving (Show)

select :: LTree a -> [Bool] -> (Maybe a)
select (Fork (Leaf a) (Leaf b)) (l:ls)  = if l==False  then Just a 
                                                       else Just b
select (Fork l r) (b:bs) = if b==False  then select l bs
                                        else select r bs

The thing is, LTree does not have declared the Empty value, how can i know that it is a node or a fork that i am falling into with my function?

解决方案

Ask the compiler

GHC can warn you about non-exhaustive patterns at compile time instead of waiting to run time to discover them. If I put your code into a file and compile it with the -fwarn-incomplete-patterns flag

ghc -fwarn-incomplete-patterns nonExhaustiveLeafTree.hs

It produces the following error message:

    Pattern match(es) are non-exhaustive
    In an equation for `select':
        Patterns not matched:
            (Leaf _) _
            (Fork (Fork _ _) _) []
            (Fork (Leaf _) (Fork _ _)) []
            (Fork (Leaf _) (Leaf _)) []

After adding the rule you suggested in your answer to cover [], it still produces a warning about anything where the tree is a Leaf _

    Pattern match(es) are non-exhaustive
    In an equation for `select': Patterns not matched: (Leaf _) _

Covering everything

We can cover all of the patterns easily if we handle Leafs and Forks separately from each other. This also removes the duplicate code of deciding which way to go on a Fork when its direct descendants are leaves.

You'll know that there's a result when you reach a Leaf and there's no path left to follow.

select (Leaf a) [] = Just a

You'll need to decide what to do when you reach a Leaf and there's still a path you need to follow.

select (Leaf a) (l:ls) = ????

Like you mentioned in your answer, you'll know there's no result when there's no path left and you are at a Fork.

select (Fork _ _) [] = Nothing

You can simplify what happens when there's a fork and a path to a single rule.

select (Fork l r) (b:bs) = if b
                           then select r bs
                           else select l bs

这篇关于Haskell中的叶子树 - 非穷举模式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！