手続き型プログラマー向けの機能コードスニペットのリスト[閉まっている]
-
07-07-2019 - |
質問
手続き型コードを機能的コードに変換しようとしても、まだ行き詰まっていることがあります。
手続き型イディオム/スニペットにマッピングされる機能的イディオム/スニペットのリストはありますか?
編集
これらのスニペットの一元化されたWebサイトがないように見えるため、これをコミュニティWikiに変えています。手続きを貼り付けてください->機能スニペットはこちら。
解決
OCaml / F#で最初にbreak / continueに到達したとき、いわば(無限)ループが発生しました。 OCamlでは、例外を使用して非常に安価であるためループから抜けることができますが、F#(.NET)ではオーバーヘッドが非常に高く、「通常」には役立ちません。フロー制御。
これは、(しばらく時間をつぶすために)しばらく前にソートアルゴリズムを使用してプレイしたときに発生しました。再帰的な末尾呼び出し関数は、読みやすさをわずかに低下させるだけで、まったく同じ結果を達成できることに気付きました。そこで、「mutable bDone」と「bnot not bDone」をスローし、これらの命令的な構成要素なしでコードを記述しようとしました。以下では、ループ部分のみを抽出し、テイルコールを使用してリピート/まで、do / while、while / do、break / continue、および中間テストスタイルのコードを記述する方法を示します。これらはすべて、従来のF# 'while'ステートメントとまったく同じ速度で実行されるように見えますが、走行距離は異なる場合があります(プラットフォームによっては、テールコールが適切に実装されず、パッチが適用されるまでフォールトがスタックする場合があります)。最後に、比較のために、両方のスタイルで記述された(悪い)ソートアルゴリズムがあります。
従来のF#命令型スタイルで記述された「do / while」ループから始めて、同じタイプのループと、while / do、repeat / until、testなどの異なるセマンティクスの両方を提供する機能バリエーションを見てみましょう途中で、さらには中断/継続(モナドなし.. um、ワークフロー!)。
#light
(* something to work on... *)
let v = ref 0
let f() = incr v;
let g() = !v;
let N = 100000000
let imperDoWhile() =
let mutable x = 0
let mutable bDone = false
while not bDone do
f()
x <- x + 1
if x >= N then bDone <- true
OK、それは十分簡単です。 f()は常に少なくとも1回(do / while)呼び出されることに注意してください。
同じコードですが、機能的なスタイルです。ここで可変を宣言する必要はないことに注意してください。
let funDoWhile() =
let rec loop x =
f() (*Do*)
if x < N then (*While*)
loop (x+1)
loop 0
ifブロック内に関数呼び出しを配置することにより、従来のdo / whileにスピンできます。
let funWhileDo() =
let rec loop x =
if x < N then (*While*)
f() (*Do*)
loop (x+1)
loop 0
ある条件が真になるまで(繰り返し/まで)ブロックを繰り返すのはどうですか?簡単です...
let funRepeatUntil() =
let rec loop x =
f() (*Repeat*)
if x >= N then () (*Until*)
else loop (x+1)
loop 0
モナドのないブレークはどうでしたか?さて、次のように 'unit'を返す条件式を導入してください:
let funBreak() =
let rec loop() =
let x = g()
if x > N then () (*break*)
else
f()
loop()
loop()
続けてどうですか?まあ、それはループへの別の呼び出しです!まず、構文crutchを使用します:
let funBreakContinue() =
let break' () = ()
let rec continue' () =
let x = g()
if x > N then break'()
elif x % 2 = 0 then
f(); f(); f();
continue'()
else
f()
continue'()
continue'()
そして(againい)構文crutchなしでもう一度:
let funBreakContinue'() =
let rec loop () =
let x = g()
if x > N then ()
elif x % 2 = 0 then
f(); f(); f();
loop()
else
f()
loop ()
loop()
パイのように簡単!
これらのループ形式の優れた結果の1つは、ループ内の状態を見つけて実装しやすくすることです。たとえば、バブルソートは、配列全体を継続的にループし、検出された場所にない値を交換します。これは、配列のパスが交換を生成したかどうかを追跡します。そうでない場合は、すべての値が正しい場所にある必要があるため、ソートを終了できます。最適化として、配列を通過するたびに、配列の最後の値が正しい場所にソートされます。そのため、ループは毎回1つずつ短縮できます。ほとんどのアルゴリズムはスワップをチェックし、「bModified」を更新します; 1つあるたびにフラグを立てます。ただし、最初のスワップが完了すると、その割り当ての必要はありません。すでにtrueに設定されています!
これは、バブルソートを実装するF#コードです(はい、バブルソートはひどいアルゴリズムです。最後に、状態を変更しない命令型実装です。交換ごとにbModifiedフラグを更新します。興味深いことに、命令型ソリューションは小さなアレイでは高速で、大きなアレイではわずか1〜2%遅くなります。 (ただし、良い例のために作成されました)。
let inline sort2 f i j (a:'a array) =
let i' = a.[ i ]
let j' = a.[ j ]
if f i' j' > 0 then
a.[ i ] <- j'
a.[ j ] <- i'
let bubble f (xs:'a array) =
if xs.Length = 0
then ()
let rec modified i endix =
if i = endix then
unmodified 0 (endix-1)
else
let j = i+1
sort2 f i j xs
modified j endix
and unmodified i endix =
if i = endix then
()
else
let j = i+1
let i' = xs.[ i ]
let j' = xs.[ j ]
if f i' j' > 0 then
xs.[ i ] <- j'
xs.[ j ] <- i'
modified j endix
else
unmodified j endix
in unmodified 0 (xs.Length-1)
let bubble_imperitive f (xs:'a array) =
let mutable bModified = true
let mutable endix = xs.Length - 1
while bModified do
bModified <- false
endix <- endix - 1
for i in 0..endix do
let j = i+1
let i' = xs.[ i ]
let j' = xs.[ j ]
if f i' j' > 0 then
xs.[ i ] <- j'
xs.[ j ] <- i'
bModified <- true
done
done
他のヒント
今、これは気の利いた質問です。以下にいくつかを示します。 Pythonのコードスニペットまたはcloe:
-
forループはイテレータに置き換えることができます
stripped_list = [line_listの行の[line.strip()]
-
forループは、apply、map、またはfilterに置き換えることができます
map(upper、['sentence'、 'fragment']) ['SENTENCE'、 'FRAGMENT']
-
関数を合成したforループのネスト
-
ループの代わりの末尾再帰
-
forループの代わりのジェネレーター式
sum(x * x for range(10)in range(10))
古い宿題の質問:
関数
(define f-imperative (y) (x) ; x is a local variable
(begin
(set x e)
(while (p x y)
(set x (g x y)))
(h x y)))
は、割り当てとループを伴う典型的な命令型スタイルです。命令型機能を使用しない同等の関数f-functionalを記述して、begin(シーケンス)、while(goto)、およびset(割り当て)を開始します。最上位ではなくletまたはletrecを使用して定義されている限り、好きなだけ「ヘルパー関数」を使用できます。
1つのソリューション:
; The idea is simple:
; Use parameter passing for binding the values
; of the variables and recursion instead of iteration.
;
; For those who like theory this is the main argument for proving
; that recursive functions (LISP, lambda calculus) have the same
; computational power as any imperative programming language.
(define f-functional (y)
(letrec (
(f-helper (lambda (x y)
(if (p x y)
(f-helper (g x y) y)
(h x y)))))
(f-helper e y)))
; Notice that y in f-helper is invariant. Therefore, we can rewrite
; f-helper without y as follows.
(define f-functional (y)
(letrec (
(f-helper (lambda (x)
(if (p x y)
(f-helper (g x y))
(h x y)))))
(f-helper e)))
; This is not the only solution, though I think it is one of the
; nicer ones.
フォールドは非常に興味深い関数であり、多くの機能アルゴリズムの中心です。リストのすべての要素を追加したいとしましょう。手続き型コードでは、通常、アキュムレータ変数を作成して0に設定し、リストを反復処理して、アイテムごとにアキュムレータをインクリメントします。
Ocamlでは、foldを使用して機能的な方法で同じアクションを実行します。
List.fold_left (+) 0 [1; 2; 3];;
- : int = 6
foldを使用すると、たとえばリスト内の単語の数を数え、それらを同時に連結できます:
List.fold_left (fun (count, concat) e -> (count + 1, concat ^ e)) (0, "") ["a"; "b"; "c"];;
- : int * string = (3, "abc")
foldのもう1つの有用な利用法は、ベクターをセットにコピーすることです。 Ocamlのセットは不変なので、リストの各アイテムに対して、前のセットとその新しいアイテムを含む新しいセットを効果的に作成する必要があります。
module Int = struct type t = int let compare = compare end;;
module IntSet = Set.Make(Int);;
let s = List.fold_left (fun set e -> IntSet.add e set) IntSet.empty [1; 2; 3];;
val s : IntSet.t = <abstr>
IntSet.elements s;;
- : IntSet.elt list = [1; 2; 3]
ここでは、初期オブジェクトは空のセットであり、呼び出しごとに、IntSet.addを使用して以前のセットと現在のアイテムに基づいて新しいセットが作成されます。
一度内部的に折りたたんで実装し、内部でどのように実行されるかを確認し、組み込みバージョンをどこでも使用します。 C ++でも、 std :: accumulate !
PLEACプロジェクトの目標はほぼ正確です。perlcookbookのすべての例を他の言語で実装します。 ocamlバージョンへのリンク(これは3つの100%完全なものの1つです) http:/ /pleac.sourceforge.net/pleac_ocaml/index.html