Rostam is preparing to confront rather _complex_ demon, with many eyes and heads. If he cut any of her n-eyed heads, she grows n-1 new heads: a k-eyed head for each k in {1,...,n-1}. The cunning warrior he is, Rostam ponders upon this task; How many heads he should sever? Does its order make any difference? Is it even possible in his mortal fini…

rostam.hs

{-# LANGUAGE UnicodeSyntax #-}

type Writer a = (a, String)
type CutMethod = [Integer] → [Integer] → [Integer]
type CutDiary = (CutMethod, Writer [Integer])

return ∷ a → Writer a
return x = (x, "")

depthFirst ∷ CutMethod
depthFirst = (++)

breadthFirst ∷ CutMethod
breadthFirst = \newHeads → \oldOnes →  oldOnes ++ newHeads

merge :: [a] -> [a] -> [a]
merge xs     []     = xs
merge []     ys     = ys
merge (x:xs) (y:ys) = x : y : merge xs ys

mergeMethod ∷ CutMethod
mergeMethod = \newHeads → \oldOnes → merge newHeads oldOnes

cut ∷ CutDiary → CutDiary
cut (c, ([], s)) = (c, ([], s))
cut (cutMethod, (h : t, s)) = cut (cutMethod, (cutMethod [1..h-1] t, s ++ (show (h : t))))

printDiary ∷ CutDiary → String
printDiary (_, (_, s)) = s