从Haskell中的二叉树中获取第N个元素

因此，从逻辑上看，我会看到这是如何工作的，但是，我找不到工作的Haskell语法来表示逻辑。这是我尝试使用嵌套后卫，这显然是不支持的功能：从Haskell中的二叉树中获取第N个元素

data Tree a where 
    Nil :: Tree a 
    Node :: Ord a => Tree a -> a -> Tree a -> Tree a 

-- Get the nth top element of a sorted binary tree: 
getNthElement :: Int -> Tree a -> Either Int a 
getNthElement _ Nil = Left 0 
getNthElement n (Node l v r) 
    | (Right x) <- rightRecurse = rightRecurse 
    | (Left nr) <- rightRecurse, nr == n = Right v 
    | (Left nr) <- rightRecurse 
    | (Right x) <- leftRecurse = leftRecurse 
    | (Left nl) <- leftRecurse = Left $ nl + nr + 1 
    where leftRecurse = getNthElement (n-nr-1) l in 
    where rightRecurse = getNthElement n r

来源

2016-02-25 clay

：在ghci中

leftInfTree :: Tree Int leftInfTree = foldr (\ k ih -> Node ih k Nil) Nil [1..]

测试守卫只对函数定义有效，我会建议使用一个case表达式。卫兵是定义函数的好语法，case是一个可以嵌入其他表达式的正常表达式。 – bheklilr

完美！固定。谢谢！ – clay

我应该删除还是等待某人回答接受？ – clay

由于bheklilr，CASE表达式解决了这个问题。工作代码为：

getNthElement :: Int -> Tree a -> Either Int a 
getNthElement _ Nil = Left 0 
getNthElement n (Node l v r) = case getNthElement n r of 
    (Right x) -> (Right x) 
    (Left nr) -> if nr == n then Right v 
       else case getNthElement (n-nr-1) l of 
        (Right x) -> (Right x) 
        (Left nl) -> Left $ nl + nr + 1

来源

2016-02-25 23:06:28 clay

这是我会怎么写呢（我的情况下，把一切都放在一个self-contained gist你想用它玩）。 State Int monad处理计数器的线程，Maybe替代选择正确的值。我认为这种算法更具可读性。

我们开始与一群进口和您的Tree定义：

{-# LANGUAGE GADTs #-} 

module NthElement where 

import Data.Functor 
import Control.Applicative 
import Control.Monad 
import Control.Monad.Trans.State 

data Tree a where 
    Nil :: Tree a 
    Node :: Ord a => Tree a -> a -> Tree a -> Tree a

然后我们在主定义到达：getNthElement运行状态计算，如果我们得到了Nothing回来了，它把参观人数节点（原始数字减去最终的Int状态），否则它将返回找到的值。

getNthElement :: Int -> Tree a -> Either Int a 
getNthElement k t = maybe (Left $ k - s) Right mv where 

    (mv , s) = go t `runState` k 

    go :: Tree a -> State Int (Maybe a)

的状态计算本身的算法，你的高层次描述直接翻译：

如果我们发现一个Nil，没有要返回的值（所以我们失败了）
```
go Nil   = return Nothing 
```
如果我们发现一个Node那么我们正在寻找的是第n个值无论是在右子树，或者在中间如果计数器0左子树探索的右子树，或某处后：
```
go (Node l v r) = do 
    rv <- go r 
    k <- get 
() <- put $ k - 1 
    lv <- go l 
    return $ rv <|> (v <$ guard (k == 0)) <|> lv 
```

通过这个定义，它不是立即清楚，我们从来没有这样做，不需要工作（我们写lv <- go l时，它可能是这个值已经被找到了！）。然而lazyness是站在我们这一边，并说服自己，这的确是好的，我们可以定义一个左无穷树，并观察getNthElement始终返回值：

*NthElement> getNthElement 10 leftInfTree 
Right 11

来源

2016-02-25 23:11:38 gallais

我尝试了这一点，它完全有效，但它似乎与状态monads，表示法和Applicative操作符复杂得多。我发布的版本使用零额外的库或类型类，它更小，更直观。 – clay

这是一个口味问题，我想。我觉得这个演示文稿对我来说更容易理解：代码中的'（Right x） - >（Right x）'分支尖叫'替代'给我。 – gallais

从Haskell中的二叉树中获取第N个元素

回答

相关问题