Еще один красивый пример

[skiminok]

Боянистый, правда, до ужаса, но тем не менее красивый.

Взять список чисел на входе. Вернуть на выходе список списков: все перестановки заданных чисел.
Иллюстрирует:

• List comprehensions
• Правую свертку
• Композицию функций

Если бы авторы F# изгнали мочу из головы и поставили, как все нормальные люди, аргумент-список в foldBack на последнее место, то иллюстрировал бы еще и частичное применение / карринг. (Правда, для этого потребуется изгнать мочу и из компилятора, а то получим радостный Value restriction, будь он неладен.)
Будучи дословно переведенным на Haskell, иллюстрирует ленивую генерацию списка. На F# для этого потребуется seq, который некрасиво пишется :-)

 let permute xs =

     let rec insert x = function 

         | [] -> [[x]]

         | y::ys -> (x::y::ys)::[for res in insert x ys -> y::res]

     List.foldBack (insert >> List.collect) xs [[]]

Работа:

> permute [1..4];;
val it : int list list =
  [[1; 2; 3; 4]; [2; 1; 3; 4]; [2; 3; 1; 4]; [2; 3; 4; 1]; [1; 3; 2; 4];
   [3; 1; 2; 4]; [3; 2; 1; 4]; [3; 2; 4; 1]; [1; 3; 4; 2]; [3; 1; 4; 2];
   [3; 4; 1; 2]; [3; 4; 2; 1]; [1; 2; 4; 3]; [2; 1; 4; 3]; [2; 4; 1; 3];
   [2; 4; 3; 1]; [1; 4; 2; 3]; [4; 1; 2; 3]; [4; 2; 1; 3]; [4; 2; 3; 1];
   [1; 4; 3; 2]; [4; 1; 3; 2]; [4; 3; 1; 2]; [4; 3; 2; 1]]

Хорошее упражнение: посчитать сложность работы permute ;)