**July 21, 2013** - Tagged as: en, haskell, ocaml.

Let’s say we want to get nth visited element in depth-first traversal of a tree. Doing this is almost too easy in a language with statements(all imperative languages, some functional ones): Just run the depth-first traversal algorithm with explicit stack, and use `return`

when you visit nth node.

In an expression language(Haskell, some Lisp languages) this is somewhat tricky.

Since I almost always prefer simplest possible solution of a problem, this would be my first attempt in a real-world situation:

```
data Tree a
= Branch [Tree a]
| Leaf a
toList :: Tree a -> [a]
toList (Branch bs) = concatMap toList bs
toList (Leaf a) = [a]
dfsNth :: Tree a -> Int -> Maybe a
dfsNth tree n = listToMaybe . drop n $ toList tree
```

One concern about this function may be that the complexity of list generation. It’s hard to predict complexity of this function, but traversing the whole tree just to get first element of it would be costly anyway.

But thanks to lazy evaluation, this function still not very bad. Because only required parts of the intermediate list will be generated. To see why you can do two things: 1) Just place some `Debug.Trace.trace`

calls in `toList`

function and see how many times a leaf node is visited and 2) evaluate this function by hand and observe unevaluated thunks.

Let’s just do the first one, since it’s easier:

```
toList :: Tree a -> [a]
toList (Branch bs) = concatMap toList bs
toList (Leaf a) = trace "leaf node visited" [a]
...
testTree = Branch [ Branch [ Leaf 1, Leaf 2 ], Branch [ Leaf 3 ], Branch [ Branch [ Branch [ Leaf 4 ] ] ] ]
```

```
ghci> dfsNth testTree 0
leaf node visited
Just 1
ghci> dfsNth testTree 1
leaf node visited
leaf node visited
Just 2
ghci> dfsNth testTree 10
leaf node visited
leaf node visited
leaf node visited
leaf node visited
Nothing
```

Other solutions are still worth exploring. When I think of “returning in the middle of a function” in Haskell, I always think `Either`

. It’s monad definition is a great fit for this:

```
instance Monad (Either e) where
return = Right
Left l >>= _ = Left l
Right r >>= k = k r
```

So when `Left data`

used in monadic bind(`>>=`

), second parameter just ignored and `Left data`

is returned. Just like returning in the middle of a function in imperative setting, by ignoring rest of statements.

Using monad instance of Either, we can easily implement our function:

```
dfsNth' :: Tree a -> Int -> Maybe a
dfsNth' tree n =
case iter tree n of
Left a -> Just a
Right i -> Nothing
where
iter :: Tree a -> Int -> Either a Int
iter (Branch []) n = return n
iter (Branch (b:bs)) n = do
n' <- iter b n
iter (Branch bs) n'
iter (Leaf a) 0 = Left a
iter Leaf{} n = return (n - 1)
```

It works exactly like our first implementation, but without generating an intermediate list.

If I were using OCaml, I’d probably implement this function using an exception.

```
exception NonLocal of int
type 'a tree =
| Branch of ('a tree) list
| Leaf of 'a
let dfs_nth tree n =
let rec iter tree n =
match tree with
| Branch [] ->
n
| Branch (b :: bs) ->
iter (Branch bs) (iter b n)
| Leaf a ->
if n = 0 then raise (NonLocal a) else n - 1
in
try
iter tree n;
None
with
| NonLocal a -> Some a
```

An interesting thing to realize here is that this solution is very similar to our Haskell solution. In Haskell, Either is an instance of `MonadError`

:

```
instance Error e => MonadError e (Either e) where
throwError = Left
Left l `catchError` h = h l
Right r `catchError` _ = Right r
```

This means if you replace `Left`

s with `throwError`

(just like `raise`

in OCaml code), you have a similar solution with OCaml.

This doesn’t mean exceptions are same thing as Either types in functional programming. There are just too many differences that I won’t delve into in this post. With an exception, you can return from arbitrary deep contexts(ie. function calls), which is not easily possible with Either types. This is why exceptions sometimes referred as *non-local returns*.

We discussed this stuff over OCaml IRC channel, and smart people over there gave me some really good insights about non-local returns and exceptions. I’ll probably delve into details in another blog post. I’m especially interested in functional solutions that we can have in Haskell.

For the curious, for now I’ll just leave these two links here: (I haven’t read that links yet, but they’re probably related)

- https://ocaml.janestreet.com/?q=node/91
- http://functional-orbitz.blogspot.se/2013/01/introduction-to-resultt-vs-exceptions.html

Several other ideas also discussed at IRC channel, some of them were using delimited continuations, or passing a handler function as parameter and just calling it instead of raising an exception. I’ll continue investigating this stuff later.

I also came across this StackOverflow post that explains how Scala’s non-local returns implemented as exceptions internally. Interesting stuff.