euler 31

[sassa_nf]

интересный урок.

сначала решение было вот такое:

split x = s x [1, 2, 5, 10, 20, 50, 100, 200]
  where s 0 _ = 1
        s x cs@(c:cs') = if x < c then 0 else ((s (x-c) cs) + (s x cs'))
        s _ _ = 0

Но беда здесь в том, что не tail call. Потом вместо (s (x-c) cs) подставил его значение, т.е. (s (x-c-c) cs) + (s (x-c) cs') и в два хода упростил до такого:

split x = length $ filter (==0) $ foldl f [x] [200, 100, 50, 20, 10, 5, 2, 1]
  where f xs c = [y | x <- xs, y <- [x,(x-c)..(x `mod` c)]]

Такой подход должен как-то называться. Где почитать?

(ну, потом вообще вот так:

split x = length $ foldl f [x] [200, 100, 50, 20, 10, 5, 2]
  where f xs c = [y | x <- xs, y <- [x,(x-c)..(x `mod` c)]]

)