-- auxiliary definitions:

concatMap = concat . map

map f [] = []
map f (x:xs) = f x : map xs

concat [] = []
concat (x:xs) = x ++ concat xs

[] (++) ys = ys
(x:xs) (++) ys = x : (xs ++ ys)

-- expansion/reduction:

perms [1,2,3]
concatMap (\xs -> helper (1:xs)) (perms [2,3])
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (perms [3]))
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concatMap (\xs -> helper (3:xs)) (perms [])))
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concatMap (\xs -> helper (3:xs)) [[]]))
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concatMap (\xs -> helper (3:xs)) [[]]))
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat . map (\xs -> helper (3:xs)) [[]]))
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat . map (\xs -> helper (3:xs)) [[]]))
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat $ helper (3:[]) : map (\xs -> helper (3:xs)) []))
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat $ helper (3:[]) : []))
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat $ helper ([3]) : []))
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat $ [[3]] : []))
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat [[[3]]]))
concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) [[3]])
concatMap (\xs -> helper (1:xs)) (concat . map (\xs -> helper (2:xs)) [[3]])
concatMap (\xs -> helper (1:xs)) (concat $ helper (2:[3]) : map (\xs -> helper (2:xs)) [])
concatMap (\xs -> helper (1:xs)) (concat $ helper ([2,3]) : [])
concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : map (3:) (helper (2:[]))) : [])
concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : map (3:) (helper ([2]))) : [])
concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : map (3:) [[2]]) : [])
concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : (map (3:) [[2]])) : [])
concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : (3:[2] : map (3:) [])) : [])
concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : (3:[2] : [])) : [])
concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : [[3,2]]) : [])
concatMap (\xs -> helper (1:xs)) (concat $ [[2,3],[3,2]] : [])
concatMap (\xs -> helper (1:xs)) (concat $ [[[2,3],[3,2]]])
concatMap (\xs -> helper (1:xs)) [[2,3],[3,2]]
concat. map (\xs -> helper (1:xs)) [[2,3],[3,2]]
concat $ helper (1:[2,3]) : map (\xs -> helper (1:xs)) [[3,2]]
concat $ helper (1:[2,3]) : helper (1:[3,2]) : map (\xs -> helper (1:xs)) []
concat $ helper (1:[2,3]) : helper (1:[3,2]) : []
concat $ helper ([1,2,3]) : helper ([1,3,2]) : []
concat $ helper ([1,2,3]) : helper ([1,3,2]) : []
concat $ ([1,2,3] : (map (2:) (helper (1:[3])))) : ([1,3,2] : (map (3:) (helper (1:[2])))) : []
concat $ ([1,2,3] : (map (2:) (helper ([1,3])))) : ([1,3,2] : (map (3:) (helper ([1,2])))) : []
concat $ ([1,2,3] : (map (2:) ([1,3] : (map (3:) (helper (1:[]))))))) : ([1,3,2] : (map (3:) ([1,2] : (map (2:) (helper (1:[]))))))) : []
concat $ ([1,2,3] : (map (2:) ([1,3] : (map (3:) (helper ([1]))))))) : ([1,3,2] : (map (3:) ([1,2] : (map (2:) (helper ([1]))))))) : []
concat $ ([1,2,3] : (map (2:) ([1,3] : (map (3:) [[1]]))))) : ([1,3,2] : (map (3:) ([1,2] : (map (2:) [[1]]))))) : []
concat $ ([1,2,3] : (map (2:) ([1,3] : (3:[1] : map (3:) []))))) : ([1,3,2] : (map (3:) ([1,2] : (2:[1] : map (2:) [))))) : []
concat $ ([1,2,3] : (map (2:) ([1,3] : ([3,1] : []))))) : ([1,3,2] : (map (3:) ([1,2] : ([2,1] : []]))))) : []
concat $ ([1,2,3] : (map (2:) ([1,3] : [[3,1]])))) : ([1,3,2] : (map (3:) ([1,2] : [[2,1]])))) : []
concat $ ([1,2,3] : (map (2:) [[1,3],[3,1]])) : ([1,3,2] : (map (3:) [[1,2],[2,1]])) : []
concat $ ([1,2,3] : (2:[1,3] : map (2:) [[3,1]])) : ([1,3,2] : (3:[1,2] : map (3:) [[2,1]])) : []
concat $ ([1,2,3] : ([2,1,3] : [2,3,1] : map (2:) [])) : ([1,3,2] : ([3,1,2] : [3,2,1] : map (3:) [])) : []
concat $ ([1,2,3] : ([2,1,3] : [2,3,1] : [])) : ([1,3,2] : ([3,1,2] : [3,2,1] : [])) : []
concat $ ([1,2,3] : [[2,1,3], [2,3,1]]) : ([1,3,2] : [[3,1,2],[3,2,1]]) : []
concat $ [[1,2,3], [2,1,3], [2,3,1]] : [[1,3,2],[3,1,2],[3,2,1]] : []
concat $ [[1,2,3], [2,1,3], [2,3,1]] : [[[1,3,2],[3,1,2],[3,2,1]]]
concat [[[1,2,3], [2,1,3], [2,3,1]], [[1,3,2],[3,1,2],[3,2,1]]]
[[1,2,3], [2,1,3], [2,3,1]] ++ concat [[[1,3,2],[3,1,2],[3,2,1]]]
[[1,2,3], [2,1,3], [2,3,1]] ++ ([[1,3,2],[3,1,2],[3,2,1]] ++ concat [])
[[1,2,3], [2,1,3], [2,3,1]] ++ ([[1,3,2],[3,1,2],[3,2,1]] ++ [])
[[1,2,3], [2,1,3], [2,3,1]] ++ [[1,3,2],[3,1,2],[3,2,1]]
[[1,2,3], [2,1,3], [2,3,1], [1,3,2],[3,1,2],[3,2,1]]

```haskell -- auxiliary definitions: concatMap = concat . map map f [] = [] map f (x:xs) = f x : map xs concat [] = [] concat (x:xs) = x ++ concat xs [] (++) ys = ys (x:xs) (++) ys = x : (xs ++ ys) -- expansion/reduction: perms [1,2,3] concatMap (\xs -> helper (1:xs)) (perms [2,3]) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (perms [3])) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concatMap (\xs -> helper (3:xs)) (perms []))) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concatMap (\xs -> helper (3:xs)) [[]])) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concatMap (\xs -> helper (3:xs)) [[]])) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat . map (\xs -> helper (3:xs)) [[]])) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat . map (\xs -> helper (3:xs)) [[]])) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat $ helper (3:[]) : map (\xs -> helper (3:xs)) [])) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat $ helper (3:[]) : [])) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat $ helper ([3]) : [])) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat $ [[3]] : [])) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) (concat [[[3]]])) concatMap (\xs -> helper (1:xs)) (concatMap (\xs -> helper (2:xs)) [[3]]) concatMap (\xs -> helper (1:xs)) (concat . map (\xs -> helper (2:xs)) [[3]]) concatMap (\xs -> helper (1:xs)) (concat $ helper (2:[3]) : map (\xs -> helper (2:xs)) []) concatMap (\xs -> helper (1:xs)) (concat $ helper ([2,3]) : []) concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : map (3:) (helper (2:[]))) : []) concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : map (3:) (helper ([2]))) : []) concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : map (3:) [[2]]) : []) concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : (map (3:) [[2]])) : []) concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : (3:[2] : map (3:) [])) : []) concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : (3:[2] : [])) : []) concatMap (\xs -> helper (1:xs)) (concat $ ([2,3] : [[3,2]]) : []) concatMap (\xs -> helper (1:xs)) (concat $ [[2,3],[3,2]] : []) concatMap (\xs -> helper (1:xs)) (concat $ [[[2,3],[3,2]]]) concatMap (\xs -> helper (1:xs)) [[2,3],[3,2]] concat. map (\xs -> helper (1:xs)) [[2,3],[3,2]] concat $ helper (1:[2,3]) : map (\xs -> helper (1:xs)) [[3,2]] concat $ helper (1:[2,3]) : helper (1:[3,2]) : map (\xs -> helper (1:xs)) [] concat $ helper (1:[2,3]) : helper (1:[3,2]) : [] concat $ helper ([1,2,3]) : helper ([1,3,2]) : [] concat $ helper ([1,2,3]) : helper ([1,3,2]) : [] concat $ ([1,2,3] : (map (2:) (helper (1:[3])))) : ([1,3,2] : (map (3:) (helper (1:[2])))) : [] concat $ ([1,2,3] : (map (2:) (helper ([1,3])))) : ([1,3,2] : (map (3:) (helper ([1,2])))) : [] concat $ ([1,2,3] : (map (2:) ([1,3] : (map (3:) (helper (1:[]))))))) : ([1,3,2] : (map (3:) ([1,2] : (map (2:) (helper (1:[]))))))) : [] concat $ ([1,2,3] : (map (2:) ([1,3] : (map (3:) (helper ([1]))))))) : ([1,3,2] : (map (3:) ([1,2] : (map (2:) (helper ([1]))))))) : [] concat $ ([1,2,3] : (map (2:) ([1,3] : (map (3:) [[1]]))))) : ([1,3,2] : (map (3:) ([1,2] : (map (2:) [[1]]))))) : [] concat $ ([1,2,3] : (map (2:) ([1,3] : (3:[1] : map (3:) []))))) : ([1,3,2] : (map (3:) ([1,2] : (2:[1] : map (2:) [))))) : [] concat $ ([1,2,3] : (map (2:) ([1,3] : ([3,1] : []))))) : ([1,3,2] : (map (3:) ([1,2] : ([2,1] : []]))))) : [] concat $ ([1,2,3] : (map (2:) ([1,3] : [[3,1]])))) : ([1,3,2] : (map (3:) ([1,2] : [[2,1]])))) : [] concat $ ([1,2,3] : (map (2:) [[1,3],[3,1]])) : ([1,3,2] : (map (3:) [[1,2],[2,1]])) : [] concat $ ([1,2,3] : (2:[1,3] : map (2:) [[3,1]])) : ([1,3,2] : (3:[1,2] : map (3:) [[2,1]])) : [] concat $ ([1,2,3] : ([2,1,3] : [2,3,1] : map (2:) [])) : ([1,3,2] : ([3,1,2] : [3,2,1] : map (3:) [])) : [] concat $ ([1,2,3] : ([2,1,3] : [2,3,1] : [])) : ([1,3,2] : ([3,1,2] : [3,2,1] : [])) : [] concat $ ([1,2,3] : [[2,1,3], [2,3,1]]) : ([1,3,2] : [[3,1,2],[3,2,1]]) : [] concat $ [[1,2,3], [2,1,3], [2,3,1]] : [[1,3,2],[3,1,2],[3,2,1]] : [] concat $ [[1,2,3], [2,1,3], [2,3,1]] : [[[1,3,2],[3,1,2],[3,2,1]]] concat [[[1,2,3], [2,1,3], [2,3,1]], [[1,3,2],[3,1,2],[3,2,1]]] [[1,2,3], [2,1,3], [2,3,1]] ++ concat [[[1,3,2],[3,1,2],[3,2,1]]] [[1,2,3], [2,1,3], [2,3,1]] ++ ([[1,3,2],[3,1,2],[3,2,1]] ++ concat []) [[1,2,3], [2,1,3], [2,3,1]] ++ ([[1,3,2],[3,1,2],[3,2,1]] ++ []) [[1,2,3], [2,1,3], [2,3,1]] ++ [[1,3,2],[3,1,2],[3,2,1]] [[1,2,3], [2,1,3], [2,3,1], [1,3,2],[3,1,2],[3,2,1]] ```