Ocamlでリストを平坦化するコードにエラーがあります

Question

こんにちはすべて私はOcamlでリストを平坦化しようとしています。私は初心者ですので、私の間違いが愚かであれば私を許してください

例えば、入力が[[1]; [2; 3]; [4]]なら、私は[1; 2; 3 ; 4]。

func flatten(list, accumalator) 
    For each item from right to left in list 
    If Item is a scalar then n :: accumalator 
    Else fi Item is a list of form head :: tail then 
       head :: flatten (tail, accumalator). 

を次のように疑似コードがあるaccumaltorと（fold_rightを使用して）右からリストを 反復を次のように私が使用しようとしていますアイデアは[] =である 私はその理論的に考えますアルゴリズムは正しいですが、あなたが同意しない場合は私に知らせてください。

今私のOCamlのコードこのアルゴリズムを実装する

let rec flatten acc x = 
    match x with 
      n -> n :: acc 
     | [x] -> x :: acc 
     | head :: remainder -> 
      head :: (my_flat acc remainder) 
and my_flat = List.fold_right flatten 
;; 

my_flat [] [[1];[2;3];[4]] 

に私が得るエラーは以下の エラー：この式は、入力した「式が、タイプ に期待された」リスト

マッチステートメントの最後のパターンのhead ::（my_flat acc remainder）という行にエラーが発生しました

助けていただければ幸いです。

Answer 1

OCamlでは、リストのすべての要素は同じ型でなければなりません。したがって、値[1; [2; 3]; 4]はそれ単独では無効です。それには、タイプintとタイプint listの2つのエレメントが含まれています。本質的に、解決すべき問題についてのあなたの記述は不可能です。

$ ocaml312 
     Objective Caml version 3.12.0 

# [1; [2; 3]; 4];; 
Characters 4-10: 
    [1; [2; 3]; 4];; 
     ^^^^^^ 
Error: This expression has type 'a list 
     but an expression was expected of type int 

これは宿題の問題のように聞こえるので、私はOCamlのに有効なリストに自分自身を制限することは、それが簡単に解決するために作ることばかり言うでしょう。

編集

OK、問題は今解決することができます！

報告されたタイプエラーの本質は、このようなものです。累計結果acc（この例ではint listのタイプ）があります。リストx（タイプもint list）を追加します。 xをhead（int）とremainder（int list）に分割しました。ご覧のとおり、my_flat関数にはremainderが適切な引数ではありません。それはint list list、すなわちintのリストのリストを望んでいる。実際には、再帰呼び出しはflattenになるはずであり、my_flatにはなりません。

私が見る別の問題：List.fold_rightの引数は、関数、リスト、および開始値です。 my_flatへのテストコールでは、最後の2つを別の順序で指定しています。空のリスト[]があなたの出発点です。

私はこれがあなたを動かすのに十分であることを望みます。 OCamlを使い始めたばかりなので、動作する前に別の問題や2つがあるかもしれません。ここで

編集2

はあなたの関数my_flatの整然とバージョンがである

....あなたはまだ独自のソリューションで作業している場合はネタバレあるかもしれないカップルより多くのコメントが、ありますList.flattenという名前のOCaml標準ライブラリ。面白いことに、実装を見てみましょう：

私はこれを非常に洗練されたソリューションと呼んでいますが、残念ながらそれはテール再帰的ではありません。だから、いくらかの（線形の）スタックスペースを消費し、非常に長いリストのためにクラッシュするかもしれません。ここで

は（トーマスで述べたように）末尾再帰動作を取得するための標準的なFPアキュムレータのトリックを使用して、同じ考え方に基づくものです：

let flatten2 ll = 
    let rec go acc = function 
    | [] -> List.rev acc 
    | l :: r -> go (List.rev_append l acc) r 
in 
    go [] ll 

しばしばそうであるように、末尾再帰バージョンは結果を蓄積します逆の順序で、そしてそれを最後に逆にする。

Answer 2

入力値のベースケースを分解することで、アルゴリズムを直接書くことができます。入力リストが空であるか、または入力リストの先頭が空である、または入力リストのヘッドは頭と尾を持っています。このコードではないので

let rec flatten = function 
    | []   -> [] 
    | []  :: t -> flatten t 
    | (x::y) :: t -> x :: (flatten (y::t)) 

あなたは、その後、機能を最適化することができますテール再帰的であり、リストが大きすぎるとクラッシュする。だから、通常の技術を使用してこれを書き換えることができます。

let flatten list = 
    let rec aux accu = function 
    | []   -> accu 
    | []  :: t -> aux accu t 
    | (x::y) :: t -> aux (x::accu) (y::t) in 
    List.rev (aux [] list) 

をだから私のアドバイスは次のとおりです。入力タイプに基づいて、あなたの問題を分解することによって開始し、その後、あなたのコードを最適化するためにアキュムレータを使用しています。ここでは、すべてのあなたの助け ため

Answer 3

おかげで、私は

let flatten list = 
    let rec flatten_each acc x = 
     match x with 
       [] -> acc 
     | head :: remainder -> head :: (flatten_each acc remainder) 
in 
List.fold_right flatten_each (List.rev list) [] 
;; 

編集この問題を解決するために使用するコードです：このソリューションは末尾再帰ではありませんトマスで指摘したように。末尾再帰バージョン私は補助機能がアキュムレータをとり、この1、リストのリストの最初の要素、およびリストのリストの残りを好き

let flatten list = 
    let rec flatten_each acc x = 
     match x with 
       [] -> acc 
      | head :: remainder -> (flatten_each (acc @ [head]) remainder) 
    in 
    List.fold_right flatten_each list [] 
;; 

Answer 4

を下回っている、それは私にとっては明確である：

let flatten list = 
    let rec aux acc list1 list2 = 
    match list1 with 
     | x :: tail -> aux (x :: acc) tail list2 
     | [] -> 
     match list2 with 
      | [] -> List.rev acc 
      | x :: tail -> aux acc x tail 
    in 
    aux [] [] list