Получить N-й элемент из двоичного дерева в Haskell

Question

Итак, логически я вижу, как это будет работать, однако я не могу найти рабочий синтаксис Haskell для выражения логики. Вот моя попытка с вложенными охранниками, которые, по-видимому, не поддерживается функция:

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 

Answer 1

Благодаря bheklilr, выражение случай решен этот вопрос. Рабочий код:

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 

Answer 2

Это, как я хотел бы написать (я положил все в self-contained gist в случае, если вы хотите играть с ним). Монашка State Int обрабатывает резьбу счетчика, альтернатива 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 то энное значение, которое мы ищем либо в правом поддереве, или в середине, если счетчик 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, когда это может быть случай, когда значение уже было найдено!). Однако ленивости на нашей стороне, и убедить себя в том, что это действительно хорошо, мы можем определить левую бесконечное дерево и наблюдать, что getNthElement всегда возвращает значение:

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

испытание в GHCI:

*NthElement> getNthElement 10 leftInfTree 
Right 11