Get Nth element from binary tree in Haskell

Question

So, logically I see how this would work, however, I can't find working Haskell syntax to express the logic. Here is my attempt with nested guards, which apparently is not a supported feature:

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

Guards are only valid on function definitions, I would recommend using a case expression instead. Guards are nice syntax for defining functions, case is a normal expression that can be embedded inside of other expressions. — bheklilr
– bheklilr, Commented Feb 25, 2016 at 21:19
should I delete or wait for someone to give an answer to accept? — clay
– clay, Commented Feb 25, 2016 at 21:34
I can post my comment as an answer, but you really did all the work — bheklilr
– bheklilr, Commented Feb 25, 2016 at 21:35

clay · Accepted Answer · 2016-02-25 23:06:28Z

1

Thanks to bheklilr, a case expression resolved this issue. The working code is:

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

answered Feb 25, 2016 at 23:06

clay

20.8k34 gold badges132 silver badges216 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

gallais · Accepted Answer · 2016-02-25 23:18:23Z

0

This is how I would write it (I have put everything in a self-contained gist in case you want to play with it). The State Int monad handles the threading of the counter, the Maybe alternative picks the right value. I think that the algorithm is more readable this way.

We start with a bunch of imports and your definition of 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

Then we arrive at the main definition: getNthElement runs the stateful computation and if we got Nothing back, it puts the number of visited nodes (original number minus the final Int state), otherwise it gives back the value it found.

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)

The stateful computation itself is a direct translation of your high-level description of the algorithm:

If we find a Nil, there is no value to return (so we fail)
```
go Nil          = return Nothing
```
If we find a Node then the nth value we are looking for is either in the right subtree, or in the middle if the counter is 0 after exploring the right subtree, or somewhere in the left subtree:
```
go (Node l v r) = do
  rv <- go r
  k  <- get
  () <- put $ k - 1
  lv <- go l
  return $ rv <|> (v <$ guard (k == 0)) <|> lv
```

With this definition it's not immediately clear that we are never doing work that is not needed (we do write lv <- go l when it might be the case that the value was already found!). However lazyness is on our side and to convince ourselves that it is indeed ok, we can define a left-infinite tree and observe that getNthElement always returns a value:

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

Test in ghci:

*NthElement> getNthElement 10 leftInfTree 
Right 11

edited Feb 25, 2016 at 23:18

answered Feb 25, 2016 at 23:11

gallais

12.1k2 gold badges34 silver badges67 bronze badges

2 Comments

clay Over a year ago

I tried this out, it completely works, but it seems much more complicated with state monads, do notation, and Applicative operators. The version I posted uses zero extra libraries or type classes, it's smaller and intuitive.

gallais Over a year ago

It's a matter of taste, I suppose. I feel like this presentation is a bit easier for me to understand: the (Right x) -> (Right x) branches in your code scream Alternative to me.

Collectives™ on Stack Overflow

Get Nth element from binary tree in Haskell

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related