从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
答
由于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
答
这是我会怎么写呢(我的情况下,把一切都放在一个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
:在ghci中
测试守卫只对函数定义有效,我会建议使用一个case表达式。卫兵是定义函数的好语法,case是一个可以嵌入其他表达式的正常表达式。 – bheklilr
完美!固定。谢谢! – clay
我应该删除还是等待某人回答接受? – clay