data Tree x = Leaf x | Node x [Tree x] data TraversalResult x = TraversalResult Int [x] dfs tree limit | limit == 0 = TraversalResult 0 [] | otherwise = case tree of Leaf x -> TraversalResult 1 [x] Node x children -> let TraversalResult num_visited result = traverse children (limit - 1) in TraversalResult (num_visited + 1) result traverse children limit | limit == 0 = TraversalResult 0 [] | otherwise = case children of [] -> TraversalResult 0 [] first : rest -> TraversalResult (visited_first + visited_rest) (result_first ++ result_rest) where TraversalResult visited_first result_first = dfs first limit TraversalResult visited_rest result_rest = traverse rest (limit - visited_first) example_tree = Node 0 [ Node 1 [Leaf 2, Leaf 3], Node 4 [Node 5 [Leaf 6]], Leaf 7 ] main = do print $ map (\limit -> let TraversalResult _ result = dfs example_tree limit in result) [1..8]