forum 275 がやっとできた。

すべての文字を各一回使ってできる文字列のパターン
http://code.nanigac.com/forum/view/275

let popped (l1, l2) =
   let rec popped' ret fr bk =
     match bk with
       []    -> ret
     | x::xs -> popped' ((x::l1, List.append (List.rev fr) xs)::ret)
                        (x::fr) xs
   in
   popped' [] [] l2
   |> List.rev;;

let all_comb l =
    let rec all_comb' = function
        (_, [])::_ as lst -> List.map (List.rev << fst) lst
      | lst -> all_comb' (List.map_concat popped lst)
    in
    all_comb' [([], l)];;

> // test run
- all_comb [0;1;2;3];;
val it : int list list
= [[0; 1; 2; 3]; [0; 1; 3; 2]; [0; 2; 1; 3]; [0; 2; 3; 1]; [0; 3; 1; 2];
   [0; 3; 2; 1]; [1; 0; 2; 3]; [1; 0; 3; 2]; [1; 2; 0; 3]; [1; 2; 3; 0];
   [1; 3; 0; 2]; [1; 3; 2; 0]; [2; 0; 1; 3]; [2; 0; 3; 1]; [2; 1; 0; 3];
   [2; 1; 3; 0]; [2; 3; 0; 1]; [2; 3; 1; 0]; [3; 0; 1; 2]; [3; 0; 2; 1];
   [3; 1; 0; 2]; [3; 1; 2; 0]; [3; 2; 0; 1]; [3; 2; 1; 0]]

うお～すげぇ！さくっとワンラインで、効率的かつわかりやすい！！
そうか。ネストさせればよかったんですね。レスありがとうございます！

ちなみに、内包表記を展開してみるとこうですね。

let popped lst = List.map (fun i -> (i, List.filter ((<>) i) lst)) lst;;

私もforum 275 をやってみました。（結構苦労しました。）
let all_comb lst =              
 let rec sub_all_c lh lt ltremain res =
  if lt = [] then res @ [lh]
  else
    match ltremain with
    | [] -> res
    | h :: t ->let t_l = [for j in lt when j <> h  -> j]
               let t_r =sub_all_c (lh@[h]) t_l t_l res              
               sub_all_c lh lt t t_r 
 sub_all_c [] lst lst [] 

あっ。わかりにくいところがあったかもしれないので補足させてください。

いきなり深さ優先探索とか幅優先探索とか言い出しましたが、これは、forum 275 を解くことってつまり木構造の探索だよね、という視点からの発言です。また、元ネタは文字列を対象とした話なのですが、リスト的なものに対する汎用な処理として解きたかったので、勝手ながら、ここでは list に対する処理として記述させてもらいました。

ちなみに、all_comb [0..3] の場合のツリーはこんな感じですね。

[] -+- [0] -+- [0; 1] -+- [0; 1; 2] - [0; 1; 2; 3]
    |       |          +- [0; 1; 3] - [0; 1; 3; 2]
    |       |
    |       +- [0; 2] -+- [0; 2; 1] - [0; 2; 1; 3]
    |       |          +- [0; 2; 3] - [0; 2; 3; 1]
    |       |
    |       +- [0; 3] -+- [0; 3; 1] - [0; 3; 1; 2]
    |                  +- [0; 3; 2] - [0; 3; 2; 1]
    |
    +- [1] -+- [1; 0] -+- [1; 0; 2] - [1; 0; 2; 3]
    |       |          +- [1; 0; 3] - [1; 0; 3; 2]
    |       |
    |       +- [1; 2] -+- [1; 2; 0] - [1; 2; 0; 3]
    |       |          +- [1; 2; 3] - [1; 2; 3; 0]
    |       |
    |       +- [1; 3] -+- [1; 3; 0] - [1; 3; 0; 2]
    |                  +- [1; 3; 2] - [1; 3; 2; 0]
    |
    +- [2] -+- [2; 0] -+- [2; 0; 1] - [2; 0; 1; 3]
    |       |          +- [2; 0; 3] - [2; 0; 3; 1]
    |       |
    |       +- [2; 1] -+- [2; 1; 0] - [2; 1; 0; 3]
    |       |          +- [2; 1; 3] - [2; 1; 3; 0]
    |       |
    |       +- [2; 3] -+- [2; 3; 0] - [2; 3; 0; 1]
    |                  +- [2; 3; 1] - [2; 3; 1; 0]
    |
    +- [3] -+- [3; 0] -+- [3; 0; 1] - [3; 0; 1; 2]
            |          +- [3; 0; 2] - [3; 0; 2; 1]
            |
            +- [3; 1] -+- [3; 1; 0] - [3; 1; 0; 2]
            |          +- [3; 1; 2] - [3; 1; 2; 0]
            |
            +- [3; 2] -+- [3; 2; 0] - [3; 2; 0; 1]
                       +- [3; 2; 1] - [3; 2; 1; 0]

蛇足ながら、思いついたことがあったので、付け加えさせてもらいます。
上の9のコードで、[for j in lt when j <> h  -> j] の部分を
[for j in lt when h < j  -> j]に直すと、比較可能な要素からなるリストを与えると、
組み合わせをリストにくるんで返す関数になります。

let all_comb3 lst len =               
  let rec sub_all_c lh lt ltremain res = 
   if ((List.length lh) = len ) then res @ [lh] 
   else 
      match ltremain with 
      | [] -> res 
      | h :: t ->let t_l = [for j in lt when h < j  -> j] 
                 let t_r =sub_all_c (lh@[h]) t_l t_l res   
                 sub_all_c lh lt t t_r  
  sub_all_c [] lst lst []  

とすると、

all_comb3 [1;2;3;4;5] 2 ;;で

val it : int list list
= [[1; 2]; [1; 3]; [1; 4]; [1; 5]; [2; 3]; [2; 4]; [2; 5]; [3; 4]; [3; 5];
   [4; 5]]
が返ります。

ご説明どうもです！しかし悲しいかな、全然頭がついていかない…(^^;;
T_GYOUTEN さんご説明で、おおよそのところはわかってきたのですが、でもコードを追えっていわれたら追えない、みたいな感じです。なので、とりあえず all_comb*N* シリーズを自分流にまとめてみました。

/// n 個から n 個選んだ順列
let perm_get_n lst =
    let rec f (h,t) brd res =
        match t, brd with
          [], _    -> res @ [h]
        | _, []    -> res
        | _, x::xs -> let ys = [ for y in t when y <> x  -> y ] in
                      f (h,t) xs (f (h@[x],ys) ys res) 
    in
    f ([],lst) lst [];;

/// n 個から m 個選んだ順列
let perm_get_m lst len =
    let rec f (h,t) brd res =
        match brd with
          _ when List.length h = len -> res @ [h]
        | []     -> res
        | x::xs  -> let ys = [ for y in t when y <> x  -> y ] in
                       f (h,t) xs (f (h@[x],ys) ys res) 
    in
    f ([],lst) lst [];;

/// n 個から m 個選んだ組合せ
let comb_get_m lst len =
    let rec f (h,t) brd res =
        match brd with
          _ when List.length h = len -> res @ [h]
        | []     -> res
        | x::xs  -> let ys = [ for y in t when y > x  -> y ] in
                       f (h,t) xs (f (h@[x],ys) ys res) 
    in
    f ([],lst) lst [];;

/// n 個から m 個選ぶ順列において、可能なすべての順列を得る
let perm_every lst =
    let rec f (h,t) brd res =
        match t, brd with
          [], _ | _, []  -> res @ [h]
        | _, x::xs       -> let ys = [ for y in t when y <> x  -> y ] in
                            f (h,t) xs (f (h@[x],ys) ys res) 
    in
    f ([],lst) lst [];;

/// n 個から m 個選ぶ組合せにおいて、可能なすべての組合せを得る
let comb_every lst =
    let rec f (h,t) brd res =
        match t, brd with
          [], _ | _, []  -> res @ [h]
        | _, x::xs       -> let ys = [ for y in t when y > x  -> y ] in
                            f (h,t) xs (f (h@[x],ys) ys res) 
    in
    f ([],lst) lst [];;

> perm_get_n [1..3];;
val it : int list list
= [[1; 2; 3]; [1; 3; 2]; [2; 1; 3]; [2; 3; 1]; [3; 1; 2]; [3; 2; 1]]
> perm_get_m [1..4] 2;;
val it : int list list
= [[1; 2]; [1; 3]; [1; 4]; [2; 1]; [2; 3]; [2; 4]; [3; 1]; [3; 2]; [3; 4];
   [4; 1]; [4; 2]; [4; 3]]
> comb_get_m [1..4] 2;;
val it : int list list = [[1; 2]; [1; 3]; [1; 4]; [2; 3]; [2; 4]; [3; 4]]
> perm_every [1..3];;
val it : int list list
= [[1; 2; 3]; [1; 2]; [1; 3; 2]; [1; 3]; [1]; [2; 1; 3]; [2; 1]; [2; 3; 1];
   [2; 3]; [2]; [3; 1; 2]; [3; 1]; [3; 2; 1]; [3; 2]; [3]; []]
> comb_every [1..3];;
val it : int list list
= [[1; 2; 3]; [1; 2]; [1; 3]; [1]; [2; 3]; [2]; [3]; []]

もうちょっとにらめっこしてみようかと思います。

ベンチマークとってみました、appendを使う方では　約57.5秒、13では0.16秒
実に360倍ほど違いがありました。へたな場所でappendを使うと、寿命がつきてしまいますね。
私はC#をずっと使ってきて、現在F#を勉強中なのですが、こいつはおもしろいですね。

マージソートも書いてみた。こんな感じかな。

let msort lst =
    let rec marge f = function x::y::ys -> f (x, y) :: marge f ys
                             | xs       -> xs
    in
    let rec sort = function xs, [] | [], xs          -> xs
                          | x::xs, y::ys when x <= y -> x :: sort (xs, y::ys)
                          | x::xs, y::ys             -> y :: sort (x::xs, ys)
    in
    let rec msort' = function _::_::_ as xs -> msort' << marge sort <| xs
                            | xs            -> xs
    in
    match msort' [for x in lst -> [x]] with [] -> [] | x::_ -> x;;

ほとんど憶測で書きますが。。
（調査に関しては最新の 1.9.4.19 でしています）

たとえば、F# において、

let add (x:T) (y:T) = x + y;;

と書いた場合、

let add (x:T) (y:T) = T.op_Addition(x, y);;

と変換されます。

しかしながら、int32 やら float やらは op_Addition メソッドを外部に公開していません。さて困った、これでは int32 や float に対して (+) が使えません。ということで、F# では、Member Constraints なる機能によってこれを回避します。(+) 演算子は、prim-types.fs で以下のように定義されています。

let inline (+) (x: ^a) (y: ^b) : ^c = 
     ((^a or ^b): (static member (+) : ^a * ^b -> ^c) (x,y))
     when ^a : int32       and ^b : int32      = (# "add" x y : int32 #)
     when ^a : float       and ^b : float      = (# "add" x y : float #)
     ...

ざっと説明すると、これは引数の型による条件分岐です。つまり、引数の型が int32 やら float やらだった場合にはそれ用の式を、それ以外の場合には op_Addition を使いましょう、ということです。

(+) の定義では、Member Constraints の対象となる型として、decimal を含みません。ですが decimal の + 演算は正しく行われます。すなわち、decimal が op_Addition を公開していて、+ 演算が op_Addition に変換されるために正しく動作するわけです。

問題は (~-) です（プレフィクスの "-" は、(~-) 演算子として prim-types.fs に定義されています）。(~-) の Member Constraints には decimal が含まれていません。このことと yuji1982 さんの事例とから考えるに、(~-) は op_UnaryNegation を使用しないのだろうと推察されます。

ここで、対応する演算子である (~+) を見てみると、Member Constraints に decimal を含んだ定義がされています。(~+) の Member Constraints に decimal が含まれているのは、(~+) が op_UnaryPlus を使わないからでしょう。であれば、なぜ、op_UnaryNegation を使用しない (~-) は、Member Constraints の対象型として decimal を含まないのか。

以上から、僕はこの挙動がバグかもしれないと疑います。

ただ、気になるのはエラー メッセージですね。「does not support any operators named '~-'」と出てもよさそうに思えますが。もしかしたら、バグじゃなくて、なにか別の理由があっての挙動なのか。。。

[参考]

http://research.microsoft.com/fsharp/manual/spec2.aspx#_T...

比較くらいなら慣れの問題で。それぞれ逆向きの演算子があるから困ることもない。

> ((<) 10) 1;;
val it : bool = false
> ((>) 10) 1;;
val it : bool = true

しかし、たとえば割り算ではどうか。

> ((/) 10.0) 5.0;;
val it : float = 2.0

(/) に対して「割られる数」を部分適用したいときはどうすればいいか。

> (fun x -> x / 10.0) 5.0;;
val it : float = 0.5

いちいち無名関数を作るのはめんどい。ということで、こんなん用意してみる。

> let __ f x y = f y x;;

val __ : ('a -> 'b -> 'c) -> 'b -> 'a -> 'c

するとこう書ける。

> (__ (<) 10) 1;;
val it : bool = true
> (__ (/) 10.0) 5.0;;
val it : float = 0.5

placeholder がほしい。