yハスケルのコンビネーター、無限のタイプ、匿名の再帰

Question

私はそれを解決しようとしていました 最大サブシーケンス合計問題 そして、ニートソリューションを思いつきました

msss :: (Ord a, Num a) => [a] -> a
msss = f 0 0

f gmax _ [] = gmax
f gmax lmax (x:xs) = 
  let g = max (lmax + x)
  in  f (g gmax) (g 0) xs

ラッパー関数を呼び出します msss, 、それは呼び出します f, 、実際に作業を行います。解決策は良好で、AFAIKは正しく動作します。何らかの理由で、生産コードの最大サブシーケンス合計問題を解決しなければならなかった場合、それが私がそれを行う方法です。

しかし、そのラッパー機能は本当に私を悩ませます。 Haskellでは、プログラム全体を単一の行に書くことができ、プログラムがほぼ1つの大きな表現であるという点を本当に駆り立てることができるように、Haskellでそれが大好きです。だから、私は余分な挑戦のためにラッパー関数を排除しようとすると思った。

今、私は古典的な問題に遭遇します：匿名の再帰を行う方法は？機能に名前を付けることができない場合、どのように再帰を行いますか？ありがたいことに、コンピューティングの父親はこの問題を何年も前に解決しました。 固定点コンビネーター, 、最も人気のあるものがあります Yコンビネーター.

Yコンビネーターのセットアップを取得するためにさまざまな試みをしましたが、コンパイラを通過することはできません。

msss' :: [Int] -> Int
msss' = (\y f x -> f (y y f) x) 
        (\y f x -> f (y y f) x) 
        (\g' gmax lmax list -> if list == [] 
                               then gmax 
                               else g' (max gmax lmax + head list) 
                                       (max 0    lmax + head list) 
                                       tail list)

ただ与える

Prelude> :l C:\maxsubseq.hs
[1 of 1] Compiling Main             ( C:\maxsubseq.hs, interpreted )

C:\maxsubseq.hs:10:29:
    Occurs check: cannot construct the infinite type:
      t0 = t0 -> (([Int] -> Int) -> [Int] -> Int) -> [Int] -> Int
    In the first argument of `y', namely `y'
    In the first argument of `f', namely `(y y f)'
    In the expression: f (y y f) x

C:\maxsubseq.hs:11:29:
    Occurs check: cannot construct the infinite type:
      t0 = t0 -> (([Int] -> Int) -> [Int] -> Int) -> [Int] -> Int
    In the first argument of `y', namely `y'
    In the first argument of `f', namely `(y y f)'
    In the expression: f (y y f) x

C:\maxsubseq.hs:12:14:
    The lambda expression `\ g' gmax lmax list -> ...'
    has four arguments,
    but its type `([Int] -> Int) -> [Int] -> Int' has only two
    In the second argument of `\ y f x -> f (y y f) x', namely
      `(\ g' gmax lmax list
          -> if list == [] then
                 gmax
             else
                 g' (max gmax lmax + head list) (max 0 lmax + head list) tail list)'
    In the expression:
      (\ y f x -> f (y y f) x)
        (\ y f x -> f (y y f) x)
        (\ g' gmax lmax list
           -> if list == [] then
                  gmax
              else
                  g' (max gmax lmax + head list) (max 0 lmax + head list) tail list)
    In an equation for `msss'':
        msss'
          = (\ y f x -> f (y y f) x)
              (\ y f x -> f (y y f) x)
              (\ g' gmax lmax list
                 -> if list == [] then
                        gmax
                    else
                        g' (max gmax lmax + head list) (max 0 lmax + head list) tail list)
Failed, modules loaded: none.

から変更 f (y y f) に f (y f) ただ与える

C:\maxsubseq.hs:11:29:
    Couldn't match expected type `[Int] -> Int'
                with actual type `[Int]'
    Expected type: (([Int] -> Int) -> t1 -> t0) -> t2 -> t0
      Actual type: ([Int] -> Int) -> t1 -> t0
    In the first argument of `y', namely `f'
    In the first argument of `f', namely `(y f)'
Failed, modules loaded: none.

コンビネーターを外部で定義するだけで別のアプローチを取ってみましたが、これはまだ機能しておらず、1つの表現でそれを行うという私の挑戦を実際に満たしていません。

y f = f (y f)

msss' :: [Int] -> Int
msss' = y (\g' gmax lmax list -> if list == [] 
                                 then gmax 
                                 else g' (max gmax lmax + head list) 
                                         (max 0    lmax + head list) 
                                         tail list)

私がしていることの何が悪いのかを見つけることができますか？私は途方に暮れています。 Haskellがそのようなことについてはすべてだったので、無限のタイプを構築することについて不平を言うのは本当に私を刻みます。それは無限のデータ構造を持っているので、なぜ無限タイプの問題があるのですか？私はそれが無量のラムダ微積分が矛盾していることを示したそのパラドックスと関係があると思います。よくわかりません。誰かが明確にすることができれば良いでしょう。

また、私は再帰が常に折り畳み関数で表現できるという印象を受けています。折りたたむだけでそれができる方法を誰かに見せてもらえますか？ただし、コードが単一の式であるという要件はまだ残っています。

Answer 1

Haskellでそのようなyコンビネーターを定義することはできません。ご存知のように、それは無限のタイプになります。幸いなことに、すでに入手可能です Data.Function なので fix, 、aを使用して定義されています let バインディング：

fix f = let x = f x in x

Answer 2

Yコンビネーターには無限のタイプが必要なので、回避策が必要です このように.

しかし、私はあなたに書くでしょう msss このようなワンライナーとして機能します：

msss = fst . foldr (\x (gmax, lmax) -> let g = max (lmax + x) in (g gmax, g 0)) (0, 0)

Answer 3

さて、それについて少し考えてみましょう。このラムダの式にはどのようなタイプがありますか？

(\y f x -> f (y y f) x)

良い f 関数です (a -> b) -> a -> b, 、 と x ある程度の価値です b. 。それは何を作りますか y？私たちが今言ったことを考えると f,

(y y f) :: (a -> b)

また、私たちはこの表現をそれ自体に適用しているので、私たちはそれを知っています y 式全体と同じタイプを持っています。これは私が少し困惑した部分です。

そう y いくつかの魔法の高次関数です。また、入力として2つの関数が必要です。だからそれは一種のようなものです y :: f1 -> f2 -> f3. f2 の形があります f, 、 と f3 上記の結果タイプがあります。

y :: f1 -> ((a -> b) -> a -> b) -> (a -> b)

問題は...何ですか f1？まあ、それはそうでなければなりません タイプのタイプと同じです y. 。これがHaskellのタイプシステムの力をどのように超えているのかわかりますか？タイプはそれ自体の観点から定義されます。

f1 = f1 -> ((a -> b) -> a -> b) -> (a -> b)

自己完結型の「ワンライナー」が必要な場合は、代わりにハマーの提案をしてください。

msss' = (\f -> let x = f x in x) 
        (\g' gmax lmax list -> case list of
            [] -> gmax
            (x:xs) -> g' (max gmax lmax + x) (max 0 lmax + x) xs
        ) 0 0

imho if max その場合、許容されます fix data.functionからも許容する必要があります。プレリュードのみのコンテストに参加していない限り。