0

OCamlを半年ほど勉強した後も、いまだに苦労していfunctional programmingますimperative programming。

についてではなくusing list or array、API の設計についてです。

たとえばstack、ユーザー向けに書き込もうとしている場合、それをどのような方法で提示する必要がありますfunctional かimperative?

stackという関数が必要popです。これは、最後の要素をユーザーに返し、スタックから削除することを意味します。だから、私が自分stackのfunctionalやり方で設計した場合、 for pop、タプルを返す必要があり(last_element, new_stack)ますよね? しかし、それは醜いと思います。

同時に、functional関数型プログラミングの方が自然だと思います。

では、この種の設計上の問題をどのように処理すればよいでしょうか。

編集

stackのソースコードを見たところ、次のように型が定義されています。

type 'a t = { mutable c : 'a list }

わかりました、内部的に標準の liblistは不変のものを使用しますが、それを変更可能なレコードにカプセル化します。

このように、ユーザーにとっては常に1つのスタックであるため、タプルをクライアントに返す必要がないことを理解しています。

それでも、それは機能的な方法ではありませんよね？

4

2 に答える 2

4

可変構造はより効率的な場合もありますが、永続的ではないため、さまざまな状況で役立ちます (主に失敗した計算をバックトラックする場合)。不変インターフェースが可変インターフェースよりもパフォーマンスのオーバーヘッドがまったくないか、ほとんどない場合は、絶対に不変インターフェースを優先する必要があります。

于 2013-07-10T11:20:40.397 に答える
1

機能的に（つまり、可変性なしで）、ポップではなくヘッド/テールを使用して正確に定義するかList、タプルを返すことでAPIに状態の変更を処理させることができます。これは、状態モナドの構築方法に匹敵します。

したがって、スタックの状態を処理するのは親スコープの責任であり (再帰などによって)、この場合、スタックはリストとまったく同じであるか、この責任の一部はタプルを介して API にロードされます。

ここに簡単な試みがあります (O'Caml 構文を知っているふりをしています):

module Stack =
  struct
    type 'a stack = 'a list
    let empty _ = ((), [])
    let push x stack = ((), x::stack)
    let pop (x::stack) = (x, stack)
      | pop _ = raise EmptyStack
  end

1 つの使用例は次のようになります。

let (_, st) = Stack.empty ()
let (_, st) = Stack.push 1 Stack.empty
let (_, st) = Stack.push 2 st
let (_, st) = Stack.push 3 st
let (x, st) = Stack.pop st

stタプルを明示的に処理する代わりに、常に渡すことを隠して、次の構文を可能にする演算子を発明したい場合があります。

let (x, st) = (Stack.empty >>= Stack.push 1 >>=
               Stack.push 2 >>= Stack.push 3 >>= Stack.pop) []

この演算子を作成できれば、状態モナドを再発明したことになります。:)

(上記のすべての関数は、カリー化された最後の引数として状態を取るため、部分的に適用できます。これを拡張して、何が起こっているかをより明確にしますが、読みにくくなります。以下の書き直しを参照してください。)

let (x, st) = (fun st -> Stack.empty st >>= fun st -> Stack.push 1 st
                                        >>= fun st -> Stack.push 2 st
                                        >>= fun st -> Stack.push 3 st
                                        >>= fun st -> Stack.pop) []

これは、少なくとも状態と不変のデータ構造を処理する慣用的な方法の 1 つです。

于 2013-07-10T12:58:04.483 に答える