CODEWITHSUNDEEP
listhaskellfunctional-programmingnested-lists
aljazfrancic
aljazfrancic

Reputation: 57

Find the most nested list

I have the following type:

data NestedList a = Elem a | List [NestedList a]

I'm trying to write a function that returns the most nested list within a given list, but I don't know where to start. Any help appreciated!

Example:

input of function is something like:

(List [List [List [List [Elem 1, Elem 2, Elem 3], Elem 5, Elem 6], List [Elem 5, Elem 6]], List [Elem 5, Elem 6]])

desired output of function:

(List [Elem 1, Elem 2, Elem 3])

Upvotes: 3

Views: 738

Answers (1)

bheklilr
bheklilr

Reputation: 54058

I'll give an example using binary trees instead, which are very similar to your structure. You'll have the exercise of converting it to work with your data type.

Say I have a binary tree

data Tree a
    = Leaf a
    | Node (Tree a) (Tree a)
    deriving (Eq, Show)

and I want to find the values that have the maximum depth (there can be more than one!). How I would solve this would be to traverse down each branch recursively, recording the depth as I go, and then return back the value(s) at the bottom along with their depth.

First, I'll define my function structure

import Data.List (sortBy, groupBy)
import Data.Ord (comparing)
import Data.Function (on)


getDeepest :: Tree a -> [a]
getDeepest tree
    = map fst                        -- Strip the depth from the values
    . head                           -- Get just the ones with the largest depth
    . groupBy ((==) `on` snd)        -- Group by the depth
    . sortBy (flip (comparing snd))  -- Reverse sort by the depth (largest first)
    $ go tree 0                      -- Find all the "bottom" nodes
    where
        go :: Tree a -> Int -> [(a, Int)]
        go (Leaf a)   n = undefined
        go (Node l r) n = undefined

This is a common recursion format you'll see in Haskell. I have a local helper function that carries an additional value that I want to initialize at a particular value, in this case the depth 0. I've already included the logic that I know I want in order to get the output in a nice format. The flip (comparing snd) will do a reverse sort, so the largest depth will come first. We then group by the depth, extract the first group, then strip the depth from the values.

Now we just have to define what go does. We know that when we hit the bottom, we want to add the value to our accumulator with the depth that we found, so

go (Leaf a)   n = [(a, n)]

That case is pretty easy, we just make a tuple from the value and the depth and wrap it as a list. For the other case, we want to traverse down each branch, find the deepest elements, and return the deepest from both branches

go (Node l r) n = go l (n + 1) ++ go r (n + 1)

This is where the recursion happens. While this is certainly not the most efficient algorithm (Haskell lists aren't great for this, but we'll use them for simplicity), it is pretty simple still. All we do is go down each side and increase our depth by 1. So the whole algorithm together:

getDeepest :: Tree a -> [a]
getDeepest tree
    = map fst                        -- Strip the depth from the values
    . head                           -- Get just the ones with the largest depth
    . groupBy ((==) `on` snd)        -- Group by the depth
    . sortBy (flip (comparing snd))  -- Reverse sort by the depth (largest first)
    $ go tree 0                      -- Find all the "bottom" nodes
    where
        go :: Tree a -> Int -> [(a, Int)]
        go (Leaf a)   n = [(a, n)]
        go (Node l r) n = go l (n + 1) ++ go r (n + 1)

So as an example:

myTree :: Tree Int
myTree =
    Node
        (Node
            (Leaf 1)
            (Node
                (Leaf 2)
                (Leaf 3)))
        (Leaf 4)

Which can be visualized as

                Node
               /    \
            Node    Leaf 4
           /    \
       Leaf 1    Node
                /    \
            Leaf 2   Leaf 3

Then by applying getDeepest to it returns [2, 3]. I encourage you to drop the type signature from getDeepest and try deleting the various functions before go tree 0 (starting at the top) so that you can see what it looks like at each step, it should help you visualize the algorithm a bit better.

Upvotes: 2

Related Questions