haskell - Find the most nested list -

i have following type:

data nestedlist = elem | list [nestedlist a] 

i'm trying write function returns nested list within given list, don't know start. appreciated!

example:

input of function 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]) 

i'll give example using binary trees instead, similar structure. you'll have exercise of converting work data type.

say have binary tree

data tree     = leaf     | node (tree a) (tree a)     deriving (eq, show) 

and want find values have maximum depth (there can more one!). how solve traverse down each branch recursively, recording depth go, , return value(s) @ bottom along depth.

first, i'll define function structure

import data.list (sortby, groupby) import data.ord (comparing) import data.function (on)   getdeepest :: tree -> [a] getdeepest tree     = map fst                        -- strip depth values     . head                           -- ones largest depth     . groupby ((==) `on` snd)        -- group depth     . sortby (flip (comparing snd))  -- reverse sort depth (largest first)     $ go tree 0                      -- find "bottom" nodes             go :: tree -> int -> [(a, int)]         go (leaf a)   n = undefined         go (node l r) n = undefined 

this common recursion format you'll see in haskell. have local helper function carries additional value want initialize @ particular value, in case depth 0. i've included logic know want in order output in nice format. flip (comparing snd) reverse sort, largest depth come first. group depth, extract first group, strip depth values.

now have define go does. know when hit bottom, want add value our accumulator depth found, so

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

that case pretty easy, make tuple value , depth , wrap list. other case, want traverse down each branch, find deepest elements, , return deepest both branches

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

this recursion happens. while not efficient algorithm (haskell lists aren't great this, we'll use them simplicity), pretty simple still. go down each side , increase our depth 1. whole algorithm together:

getdeepest :: tree -> [a] getdeepest tree     = map fst                        -- strip depth values     . head                           -- ones largest depth     . groupby ((==) `on` snd)        -- group depth     . sortby (flip (comparing snd))  -- reverse sort depth (largest first)     $ go tree 0                      -- find "bottom" nodes             go :: tree -> int -> [(a, int)]         go (leaf a)   n = [(a, n)]         go (node l r) n = go l (n + 1) ++ go r (n + 1) 

---

so example:

mytree :: tree int mytree =     node         (node             (leaf 1)             (node                 (leaf 2)                 (leaf 3)))         (leaf 4) 

which can visualized as

                node                /    \             node    leaf 4            /    \        leaf 1    node                 /    \             leaf 2   leaf 3 

then applying getdeepest returns [2, 3]. encourage drop type signature getdeepest , try deleting various functions before go tree 0 (starting @ top) can see looks @ each step, should visualize algorithm bit better.