3

こんにちは、Ocaml でリストをフラット化しようとしています。私は初心者なので、私の間違いがばかげている場合はご容赦ください

たとえば、入力が [[1];[2;3];[4]] の場合、[1;2;3;4] になります。

私が使用しようとしているアイデアは次のとおりです 右からリストを反復処理します (fold_right を使用) with accumaltor = [] 擬似コードは次のとおりです

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).

理論的にはアルゴリズムは正しいと思いますが、そうでない場合はお知らせください。

次に、このアルゴリズムを実装するための 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]]

私が得るエラーは次のエラーです: This expression has type 'a but an expression was expected of type 'a list

エラーは、match ステートメントの最後のパターンで head :: ( my_flat acc Removal ) を読み取る行で発生します。

どんな助けでも大歓迎です。

4

4 に答える 4

4

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

$ 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）をリストに追加します。あなたは（an ）と（an ）xに侵入しました。ご覧のとおり、は関数に適した引数ではありません。つまり、intのリストのリストが必要です。実際、再帰呼び出しはほぼ確実にに行くべきであり、に行くべきではありません。headintremainderint listremaindermy_flatint list listflattenmy_flat

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

私はこれがあなたを動かすのに十分であることを願っています。あなたはOCamlを始めたばかりなので、それが機能する前におそらく別の問題が1つか2つあるでしょう。

編集2

ここにさらにいくつかのコメントがあります。これは、まだ独自のソリューションに取り組んでいる場合はネタバレになる可能性があります。

あなたの関数のよりきちんとしたバージョンはmy_flat、OCaml標準ライブラリにという名前でありList.flattenます。実装を見るのは興味深いです：

let rec flatten = function
    [] -> []
  | l::r -> l @ flatten r

これは非常にエレガントなソリューションと呼んでいますが、残念ながら末尾再帰ではありません。そのため、（線形の）スタックスペースを消費し、非常に長いリストの場合でもクラッシュする可能性があります。

これは同じ考えに基づいたもので、標準のFPアキュムレータトリックを使用して末尾再帰の動作を取得します（Thomasが指摘）：

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

よくあることですが、末尾再帰バージョンは結果を逆の順序で累積し、最後に逆にします。

于 2012-02-10T04:54:17.537 に答える
2

私はこれが好きです。補助関数がアキュムレータ、リストのリストの最初の要素、およびリストのリストの残りの部分を取るところ、それは私にとってより明確です:

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
于 2012-02-14T23:08:29.133 に答える
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)

したがって、私のアドバイスは、入力タイプに基づいて問題を分解することから始め、後でアキュムレータを使用してコードを最適化することです。

于 2012-02-10T11:05:13.633 に答える
1

ご協力いただきありがとうございます。この問題を解決するために使用したコードは次のとおりです。

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 ) []
;;

編集：トーマスが指摘したように、このソリューションは末尾再帰ではありません。テール再帰バージョンは以下です

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 []
;;
于 2012-02-12T01:44:32.250 に答える