list - Reverse Monkey Puzzle sort (Haskell) -

i have repeat in haskell in augest i'm trying practice haskell. 1 of questions is:

"a reverse monkey puzzle sort of list performed storing elements of list binary tree , traversing tree nodes of subtree visited in order right child, parent , left child. write reverse monkey puzzle sort in haskell"

the question confuses me. know have write function go xr node xl. have output list traversed tree? or repopulate binary tree list or what? also, start down in farthest right element , go that's parent go left, or start @ first root node @ top of tree , go way?

also how go writing it, haskell 1 of weak points. appreciate this!

here code have

module data.btree  data tree = tip | node (tree a) (tree a) deriving (show,eq)  leaf x = node x tip tip  t1 = node 10 tip tip t2 = node 17 (node 12 (node 5 tip(leaf 8)) (leaf 15))          (node 115                 (node 32 (leaf 30) (node 46 tip (leaf 57)))                 (leaf 163)) t3 = node 172 (node 143 (node 92 (node 76 (leaf 32) (leaf 45)) (node 58 (leaf 39) (leaf 52))) (node 107 (node 92 (leaf 64) (leaf 35)) (node 86 (leaf 69) (leaf 70))))           (node 155 (node 127 (leaf 83) (leaf 97)) (node 138 (leaf 107) (leaf 91))) 

you can write

data tree = empty | tree (tree a) (tree a)  ins :: ord => tree -> -> tree ins empty x = tree empty x empty ins (tree l y r) x = if x < y tree (ins l x) y r else tree l y (ins r x)  fromlist :: ord => [a] -> tree fromlist = foldl ins empty -- <<< foldable  tolist :: ord => tree -> [a] tolist empty = [] tolist (tree l x r) = (tolist l) ++ [x] ++ (tolist r) -- <<< monoid                                                       -- (change order if wish)  sort :: ord => [a] -> [a] sort = tolist . fromlist 

to solve directly problem.

in general useful use more abstract structures monoid, foldable, ... can (must) read learn haskell great good!

:)

example

*main> sort [6, 3, 7, 8, 3, 6] [3,3,6,6,7,8] 

as commented (into code), 1 more general way it, define useful structs tree: foldable, monoid , others.

suppose have 2 structs implemented:

import data.foldable import data.monoid  data tree = empty | tree (tree a) (tree a) deriving show  -- shortcut leaf :: ord => -> tree leaf x = tree empty x empty  instance foldable tree     foldmap f empty = mempty     foldmap f (tree l k r) = foldmap f l `mappend` f k `mappend` foldmap f r  -- warning: in monoid traverse result (ordered list) invariant! instance ord => monoid (tree a)     mempty = empty     mappend empty tree = tree     mappend tree empty = tree     mappend (tree l x r) tree = ins (l `mappend` r `mappend` tree) x         ins empty x = leaf x               ins (tree l y r) x = if x < y tree (ins l x) y r else tree l y (ins r x) 

that usual in haskell.

now, problem (define sort on lists using load/unload tree) simply:

sort :: ord => [a] -> [a] sort = foldmap return . foldmap leaf 

a more general way (struct) detailed @m0nhawk, @tel , @petr-pudlak in this question