Löbとmöb：Haskellの奇妙なループ

これは記事のかなり無料の翻訳です。 実際には、1行で構成されているにもかかわらず、その素材を理解することは困難です。
PreludeのコメントまたはHaskellを愛する方法で、彼らはコードを明確にするように頼み、十分な発言をしたことを考慮し、Haskellから遠く離れた人にはコードが明確になることを願っています。

最も難しいものから始めましょう-見出し自体から：多くは彼の言葉をすべて理解していません。
Haskellは、クリーンで怠functionalな関数型言語です。
ローブはドイツの数学者であり、これについては後ほど説明します。
そして最後に、最も興味深いのは奇妙なループです。

ストレンジループは混乱を招くカテゴリです。階層システムで上下に移動すると、移動を開始した場所と同じものが見つかります。
多くの場合、このようなループには自己参照リンクが含まれています。
たとえば、再帰的な頭字語には、「PHP-PHP：Hypertext Preprocessor」という奇妙なループがあります。
さて、これまでのところ、奇妙なループを含む最も神秘的な言葉は「I」の概念です。

奇妙なループは、その美しさで人々を興奮させます。 そして、あなたが最も予期しない場所でそれらを見つけるとき、それは非常に素晴らしいです。 Haskellでは、奇妙なループを持つ非常に興味深い関数を作成できます。

ドイツの数学者ローブは、20世紀の39年に英国に移住しました。 特にローブは数学的論理を開発し、世界は主にローブの定理で知られています。 この定理は、数学の不完全性に関するゲーデルの研究を発展させました。 声明の証明可能性と声明自体の関係に関するローブの定理は、

Peanoの公理（自然数に関する公理）を含む理論では、ステートメントPについては、ステートメントP証明可能である場合にのみ、「 P証明可能な場合、 P真」というステートメントの証明可能性が可能です。

ステートメントのこの複雑さはすべて象徴的に書くことができます。


Haskellでそのような関数を書くことは可能ですか？！ できます！ そして、たった1行です！

ローブ

loebはHaskellのこれらの機能の1つで、魅力的で、クレイジーで、シンプルで、同時に複雑に見えます。

1. 関数を書くのはとても簡単です
2. 機能がわかりにくい
3. 使いやすい機能
4. 関数は説明可能です

実装

スマートに感じますか？ これを変更して、 loeb関数を提示しましょう。

 loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap ($ go) x 

すべての美しさを感じますか？！ 次に、次のセクションに進みます。
いや？ うーん...多分あなたはちょうどHaskellをよく知らないのですか？ 次に、より詳細に説明します。
賢い人の中には、なぜ1行ではなく2行あるのかを尋ねる人もいますが、彼らは正しいでしょう。 しかし、部分的にのみ。 実際、最初の行は署名です：アナウンスメント、タイプ、機能のパラメーター数。 ただし、この行はオプションです-記述しない場合、インタープリター（およびコンパイラー）自体が型を派生します。

 loeb :: Functor f => f (fa -> a) -> fa 

署名は3つの部分に分かれています-最初に関数の名前を書き、次に型を宣言したいということを言ってから::太字の矢印（ => ）に入れて、パラメーターに制限を書きます-それが重要になるまで、以下で少し説明します そして最後に-実際には、タイプ：
f (fa -> a) -> fa 、レコードがローブの定理にどれだけ近いかを調べます。 -はい、1対1！
ライブラリ関数を使用せずに関数が作成されたことに注意してください！

署名の意味を説明する前に、関数自体を検証する限り、適切なHaskelistが行うように、時間を無駄にせずに3行で関数を記述しましょう。

 loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap ($ go) x 

ここで、 whereという単語はサービスワードであり、内部関数を定義できるようにします。

読み方？...そうそう、Haskellには余分な括弧はなく、ほとんどの言語はどこに書くかを言わなければならない
f (x, y, z) = ... 、Haskellではfxyz = ...のみをfxyz = ...

コードから、 loeb関数は1つの引数関数であり、 go関数によって決定されることがloebます。

go関数は、Functorおよびfmap関数を介して定義されます。 fmap関数自体は、リストのmap関数の一般化であり、次のように定義されます。

 class Functor f where fmap :: (a -> b) -> fa -> fb 

これは単なる宣言です。 OOPクラスは、決して型クラスに関連付けられていません。 この場合、最初の行を実際に理解する必要はありませんfmap関数でfがポリモーフィックになるというだけです。
それでは、署名を注意深く見て、その意味を理解しましょう。
fmap関数は2つの引数の関数- (a -> b) fa (a -> b)とfaと言われ、出力はfbです。
(a -> b) a- (a -> b)はいくつかの入力を取る単一の引数の関数であり（通常、このタイプをaと呼びます。たとえば、文字列、数値、またはファイル）、出力も次のようになります。または入力します（特にbである可能性がaことに注意して、 bで表します）。
fa - a依存する複雑な値として理解でき、 f(a)読むと理解しやすくなります。
数学でファンクターの定義を開くと、驚くほどの類似性がわかります。
つまり、完全な理解から注意をそらして直感に目を向けると、 fmap関数がfを介して値に関数を適用することがわかります。これは原則として当てはまります。

必要に応じて、ファンクターの全機能を完全に理解する必要はありません。リストを見てみましょう。

 instance Functor [] where fmap = map 

ここで簡単に判明しました-リストの場合、 fmap関数fmap map関数に完全に似ていmap 。 さて、すべてのmapすでにmap関数を知っていmap 。これはリストのすべてのメンバーへの関数の適用です。 Haskellでは、非常に簡単に定義されています：

 map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = fx : map f xs 

シグネチャを見てみましょう。ここではすべてが既におなじみです-2つの引数の関数-1つのパラメーターの関数とリスト。 その結果、変更されたリストを取得します。
2行目は、関数に関係なく空のリスト（「_」-これにより、その値を知る必要がないと言います）には空のリストがあることを示しています。
その他の場合、リストを先頭と残りに分割し（ x : xs 、文字sに注意、英語では複数、おそらくxsが多いことを意味する）、別のリストを返します。ここで、先頭に関数を適用し、尾、説明した関数を再帰的に適用します。



さて、再び定義に移りましょう。

 go = fmap ($ go) x 

ドルの機能は何ですか？ アンクル・サムがいなくても可能ですか？ まあ、あなた、それは純粋な言語です！ $は、適用関数と呼ばれる通常の演算子関数であり、基本的に定義されます。

 ($) :: (a -> b) -> a -> b f $ x = fx 

いいえ、アプリケーション関数は何もしませんが、括弧の代わりに使用されることがよくあります。

混乱しないように、ラムダ式を使用してloeb関数を書き換えます。

 loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap (\z -> z go) x 

ラムダ式を読むのは簡単です： \z -> z goは、1つの変数zからラムダ関数（スラッシュはギリシャ文字lambda- λ似ています）を意味しますが、矢印->として読む=

素晴らしい、私たちは読むことができました！ 今ではそれを理解することが残っています！

loebは何をしますか？

短いバージョン： loebはそれ自体で結果を計算しますが、再帰について最初に聞いたときに感じたものよりもクレイジーです。

詳細バージョン： loeb使用するloeb どこで便利ですか？ たとえば、リストファンクターのスプレッドシート（​​Exelなど）を作成できます-[]：

 xs :: [a] xs = [...] fs :: [[a] -> a] fs = [...] rs :: [a] rs = [ f xs | f <- fs ] -- r = f xs 

リストxs :: [a]ます。 そして、リストを値fs :: [[a] -> a]折りたたむ関数のリストがあります。 リストから関数ごとに要素のリストに適用し、 r新しい値を取得します。 リストrsすべてのrを収集します。

 [ f xs | f <- fs ] 

理解することは困難ですが、それでもなお、リストの各セルで（リストから）関数を値のリストに適用すると、右から左に読み取られます。

これらのアクションに基づいて、 xs値のリストとfs関数のリストからrsを計算しました。

そして今、最も重要なことxs値のリストを取得することはできませんが、代わりにrs使用してください。 言い換えれば、関数fは結果のリストに適用され、それ自体が生成します！

 fs :: [[a] -> a] fs = [...] rs :: [a] rs = [ f rs | f <- fs ] 

もちろん、これはすべて極端な遅延に依存しますが、 rsはそれ自体で計算されます。 fs独自の定義を持たないように両方の関数を組み合わせることができ、それらはrs単なるパラメータになります。

 rs fs = [ f (rs fs) | f <- fs ] 

よく見ると、リストの場合rs = loeb

したがって、関数loeb関数のリストを受け取り、生成した結果のリストを計算し、生成されたばかりのリストに自分自身を適用します。 変なの？ チェックしてみて？ ループしていますか？ 違います！

loeb

この関数の使用方法を理解するのに役立つ例：

 fs = [ const 1 , succ . (!! 0) , succ . (!! 1) , succ . (!! 2) ] 

ここでconst a _ = aは常に最初の値を返す2つの変数の関数であり、 succ x = inc数値の増分（より正確には、列挙値の増分の一般化です）、 (!!)はリストからn要素を取得する関数です、 (.) -2つの機能の機能的構成(.)最初に正しい機能を適用し、次に左側の機能を使用します。この場合、最初にリストから項目を取得し、次に増分します。

ここでは、以前の結果に関して要素のリストを説明しました。 const 1には最初の要素があり、常に1を返します。その後、2番目の要素（ succ . (!! 0)値を取得できますsucc . (!! 0) succ . (!! 0) 、さらにチェーンに沿って-3番目、4番目、5番目。

 > loeb fs [1,2,3,4] 

興味深いのは、順序が必ずしも左から右である必要がないことです。 順序は逆にすることができ、主なことは循環再帰を達成しないことです（この場合、関数は計算を終了できません）。

 fs = [ succ . (!! 1) , succ . (!! 3) , succ . (!! 0) , const 1 ] > loeb fs [3,2,4,1] 

真実はスプレッドシートのように見えますか？！ セル内の1つの値は既知であり、残りは何らかの形で互いに依存しています。 計算が終了すると、各セルに特定の値が設定されます。 固定小数点コンビネーターの一般化のように見えます。

スプレッドシート！

上記の例は、1次元のテーブルに似ています。 ただし、現実に近い他のファンクタ、たとえば配列を使用することもできます！

 import Data.Array import Data.List import Control.Monad import Text.Printf loeb :: Functor f => f (fa -> a) -> fa loeb x = go where go = fmap ($ go) x --   e = val 0 --     val = const -- ,   (10 %)    vat ix = (* 0.1) . (! ix) --    sum' ixs = \arr -> foldl' (\acc ix -> acc + arr ! ix) 0 ixs spreadsheet = listArray ((0,0), (4,4)) -- Prices | VAT | Effective prices + total [ val 1, vat (0,0), sum' [(0,i) | i <- [0..1]], e, e , val 3, vat (1,0), sum' [(1,i) | i <- [0..1]], e, e , val 5, vat (2,0), sum' [(2,i) | i <- [0..1]], e, e , val 2, vat (3,0), sum' [(3,i) | i <- [0..1]], e, e , e, e, sum' [(i,2) | i <- [0..3]], e, e ] printArr :: Array (Int, Int) Double -> IO () printArr arr = forM_ [0..4] $ \i -> do forM_ [0..4] $ \j -> printf "%4.1f " (arr ! (i,j)) printf "\n" main = printArr $ loeb spreadsheet 

実行しましょう！
出力では次のようになります。

  1.0 0.1 1.1 0.0 0.0 3.0 0.3 3.3 0.0 0.0 5.0 0.5 5.5 0.0 0.0 2.0 0.2 2.2 0.0 0.0 0.0 0.0 12.1 0.0 0.0 

ここで、最初の膝には価格（ valを使用）があり、2列目には左側の税金があり、3列目には実効価格があり、以下はすべての実効価格の合計金額です。 これで、すべてを確認、注文、購入できます！ 魔法！ :-)

moeb関数

moebは、 loeb関数の定義を使用したゲームの結果ですloeb関数を無視する場合はどうなりますか。 まず第一に、これは関数の署名をただ狂わせるでしょう！

 -- [m]oeb = multi-loeb :-) moeb :: (((a -> b) -> b) -> c -> a) -> c -> a moeb fx = go where go = f ($ go) x 

そして、新しい用語では、 loebを再定義することができます、それはmoeb特別なケースにmoebます：

 loeb = moeb fmap 

また、 moeb関数のパラメーターに使用できる他の関数は何ですか？
たとえば、関数がある場合

 id :: a -> a id x = x 

次に：

 moeb id x = id ($ moeb id x) x = ($ moeb id x) x = x (moeb id x) --    ,   fix -- fix f = f (fix f) fix = moeb id 

ご覧のとおり、 moebはfix関数の一般化です。

moebパラメーターとして使用できる他の関数（ traverseやfoldMapなど） traverseありfoldMap 、これに何が役立つかはまだわかりません。