8

私は最大部分列和問題を解決しようとしていて、ネイトの解決策を思いつきました

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れ、実際に処理が実行されます。解決策は良好で、正しく機能しています。なんらかの理由で、製品コードで最大部分列和問題を解かなければならない場合、それが私のやり方です。

しかし、そのラッパー関数は本当に私を悩ませます。Haskell では、プログラム全体を 1 行で書くことができるほど粘り強く、プログラムがほとんど 1 つの大きな式に過ぎないという点を真に強調する方法が気に入っています。そこで、余分な課題のためにラッパー関数を排除しようと考えました。

今、私は古典的な問題に遭遇しました: 匿名の再帰を行うには? 関数に名前を付けることができない場合、どのように再帰を行いますか? ありがたいことに、コンピューティングの父たちはずっと前に固定小数点コンビネーターを発見することでこの問題を解決しました。最も人気のあるものは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 はそういうものばかりだと思っていたからです。無限のデータ構造を持っているのに、なぜ無限型に問題があるのでしょうか? 型付けされていないラムダ計算が矛盾していることを示したパラドックスと関係があると思います。よくわかりませんが。誰かが明確にできれば良いでしょう。

また、再帰は常にfold関数で表現できるという印象を受けました。折り目を使用するだけでそれを行う方法を誰かに教えてもらえますか? ただし、コードが単一の式であるという要件は依然として有効です。

4

3 に答える 3

9

Haskell のように Y コンビネータを定義することはできません。お気づきのとおり、それは無限型になります。幸いなことに、バインディングを使用して定義されているData.Functionasで既に利用可能です。fixlet

fix f = let x = f x in x
于 2011-11-29T09:40:17.287 に答える
7

Y コンビネータには無限の型が必要なため、このような回避策が必要になります。

しかし、私はあなたのmsss関数を次のようなワンライナーとして書きます:

msss = fst . foldr (\x (gmax, lmax) -> let g = max (lmax + x) in (g gmax, g 0)) (0, 0)
于 2011-11-29T10:03:11.787 に答える
6

ちょっと考えてみましょう。このラムダ式の型は何ですか?

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

Wellfは関数(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 ifmaxは許容されますが、fixfrom Data.Function も許容されるはずです。プレリュードのみのコンテストに参加している場合を除きます。

于 2011-11-29T18:27:24.227 に答える