6

3 桁の数の積の中から最大の回文を見つける次の命令型コードを考えてみましょう (そうです、これは「[18 世紀の傑出した数学者] のプロジェクト」サイトの最初のタスクの 1 つです)。

curmax = 0
for i in range(999,100):
for j in range(999,100):
    if ((i*j) < curmax): break
    if (pal(i*j)):
        curmax = i*j
        break
print curmax

私は現在 Haskell を学んでいるので、私の質問は、これ (および、基本的には単純な反復よりも複雑なものを含む命令型構造、たとえば、中断、継続、一時変数など) を Haskellにどのように変換するのかということです。

私のバージョンは

maxpal i curmax
    | i < 100 = curmax
    | otherwise = maxpal (i-1) (innerloop 999)
    where 
        innerloop j
            | (j < 100) || (p < curmax) = curmax
            | pal p = p
            | otherwise = innerloop (j-1)
            where p = i*j
main = print $ maxpal 999 0

しかし、これはまだ命令的な醜い町にいるようです。

では、そのような場合に FP スタイルで対処する方法について、アドバイスをいただけますか?

4

9 に答える 9

7

ダニエルとsepp2kの同様の答え：

遅延関数型プログラミングを使用すると、質問のような命令型制御フローで見られるよりもはるかにモジュール化された方法でプログラムを作成できます。たとえば、係数 999...100 のリストを作成し、次にすべての積を作成し、回文のみを保持するようにフィルター処理してから、最大値を計算します。lazinessのおかげで、これらの中間リストは必要な場合にのみ作成され、段階的に再利用されます。

詳しい説明と例については、John Hughes の古典的な論文Why Functional Programming Mattersを参照してください。

maxpal :: Int
maxpal = maximum [i*j | i <- factors, j <- factors, pal (i*j) ]

factors :: [Int]
factors = [999,998..100]

pal :: Show a => a -> Bool
pal = palL . show

palL :: (Eq a) => [a] -> Bool
palL xs = xs == reverse xs
于 2010-12-22T19:29:31.437 に答える
5

すべての最適化をやめて、100 から 999 までの数字のすべての組み合わせを乗算し、非回文を除外してその最大値を取ると、次のように関数を非常に簡潔に書くことができます。

maximum $ filter pal [x*y | x <- [100..999], y <- [100..999]]

もちろん、これは基本的に最も効率の悪い方法ですが、数値が比較的小さいため、私のマシンでは 0.5 秒未満で終了します。

ただし、アルゴリズム的に python ソリューションのラインに沿ったものが必要な場合は、次のようにすることができます。

import Data.Maybe
import Data.List

maxpal i curmax
    | i < 100 = curmax
    | otherwise = maxpal (i-1) newmax
    where newmax = fromMaybe curmax (find pal bigger)
          bigger = takeWhile (> curmax) (map (*i) [999, 998 ..])

ここで、外側のループは基本的にソリューションと同じですが、代わりにリスト関数を使用して内側のループを置き換えました。

からのカウントダウンごとmap (*i) [999, 998, ...]に製品を作成するために使用しています。を使用すると、値が を超えなくなったらリストを停止する必要があると言っています。i*jj999takeWhilecurmax

次にfind、そのリスト内の項目が回文であるかどうかを確認するために を使用しています。そうであれば、リストの最初の回文が新しい最大値です。そうでない場合は、古い最大値を維持します。( finda を返し、デフォルト値を受け取り、 aMaybeから値を返すか、 に値がない場合はデフォルト値を返します)fromMaybeMaybeMaybeMaybe

于 2010-12-22T19:28:00.693 に答える
2

したがって、機能的に考えると、問題をループやステップではなく関数に分割する方法を検討する必要があります。

したがって、真となる最大値を返す関数がmaxWhere f xsある場合、次のように書くことができます。xf x

maxpal = maxWhere pal [x * y | x <- [999,998..100], y <- [999,998..100]]

maxWhere の素朴な実装は

maxWhere f xs = maximum $ filter f xs

しかし、オリジナルよりも多くの f を呼び出すことになるため、 iffは比較よりもコストがかかります。フォールドを使用してフィルターと最大値を 1 つのパスに結合し、命令型コードと同じ動作を得ることができます。

maxWhere f xs = foldl' r 0 xs
    where r a x
       | x > a     = if f x then x else a
       | otherwise = a

ここで魔法の小数としてゼロを使用するのは恐ろしいことですが、その場合はうまくいきます。

(私は本当にその候補番号のリストを綴りたいのです(*) <$> [999,998..100] <*> [999,998..100]が、それはここで不必要な複雑さを導入している可能性があります.)

于 2010-12-22T22:58:32.823 に答える
2

私の考えでは、範囲はリストに対応します。例えば：

f = [999,998..100]

現在fは、999 か​​ら 100 までの一連の数字として定義されています。

forループは、各反復で何をしているかに応じて、さまざまな機能概念に対応しています。amapが適切なアナログである場合もあれば、 afoldである場合もあれば、他の何かである場合もあります。多くの場合、それは物事の組み合わせです。この場合、効果的に 2 つのリストを結合しています。Haskell でこれを行う 1 つの方法は、リスト内包表記です。

g = [(x * y) | x <- f , y <- f]

ここでgは、以前に定義されたシーケンスの各要素とそれ自体を組み合わせた積のリストを表します。言い換えれば、forループ内で起こっていることのほとんどです。

ここから、結果のシーケンスをフィルター処理して、回文である値のみを含め、そのセットから最大値を計算することをお勧めします。

于 2010-12-22T19:19:56.730 に答える
2

ここには万能の答えはありません。しかし、次の具体的な例を見てみましょう。

まず、外側のループを考えてみましょう。常に全範囲を処理し、最終的な最大値のみを気にするので、簡単です。

outerLoop = foldl innerLoop 0 [999,998..100]

内側のループには、i の値と現在の最大値があります。ここで、i*j が現在の最大値よりも大きい範囲のみを考慮します。

innerLoop curmax i = foldr checkMax curmax [999*i, 998*i .. curmax]

コア ロジックでは、常に現在の最大値以上であることがわかっている i*j の値を取得するため、次の値をチェックして回文であるかどうかを確認するだけです。これは、シーケンスが減少するためです。そうでない場合は、決定を延期します。

checkMax ij defer = if pal ij then ij else defer
于 2010-12-22T19:47:20.523 に答える
1

ガッ。sepp2k に負けましたが、一般的な質問にお答えします。

一時変数は、状態モナドや ST モナドを使って表現することもできます。多くの場合、FP は簡潔さと明快さの点で優れていますが、うまくいかない場合もあります。たとえば、複数のローカル変数を扱う場合などです。

怠惰は多くの中断をエミュレートできますが、IO を扱うときは、通常、明示的な再帰を使用する必要があります。ただし、'List' パッケージ (Hackage から) は、機能的なスタイルで IO ループを記述できる点でかなり優れています。

于 2010-12-22T19:40:43.960 に答える
1

この種のループは、次のようなリスト内包表記に簡単に役立ちます。

maximum [x*y | x <- [999..100], y <- [999..100],isPalindrome (x*y)]

isPalindrome は次のように記述できます。

isPalindrome x = xs == reverse xs
  where xs = show x

これは非常に高速ですが、一種のスマートではないため、まず最初に、数値を 2 回チェックしていることに気付くでしょう。a*b が最大の回文であるとしましょう。その場合x == a, y==b、 との両方のケースをチェックしx==b, y==aます。まず、次のように、検索する数値を x >= y の場合のみに制限することで、これを停止します。

maximum [x*y | x <- [999..100], y <- [x..100],isPalindrome (x*y)]

これにより、テストする数が半分になります。

あなたのpythonソリューションでは、これまでに見つかった最大の数を現在のx（x*y => curmax）で割った値でyを下にバインドし、最初に見つかったyを超えて検索することもありません（curmaxが更新された場合、内部ループを壊します）。チェックする最初の要素 (x の 2 乗) が現在の答えよりも小さい場合は、続行しないことで検索をさらに削減できます。これは、後続のすべてのチェックが小さいためです。それは独自の機能です：

import Data.List(find)
import Data.Maybe(isNothing,fromJust)

search x curr 
   | x * x < curr                   = curr
   | isNothing maypal || pal < curr = search (x - 1) curr 
   | otherwise                      = search (x - 1) pal 
   where maypal = find isPalindrome [x * x, (x - 1) * x .. curr]
         pal    = fromJust maypal

私たちの制限である が、これからは空になることを(x*x) < curr意味していることに注意してください。[x*x,(x-1)*x..curr]ご覧のとおり、Python コードのブレークによって強制されたすべての境界は、x の 1 回の反復 (再帰を使用) と x*y 値のリストの検索に収まります。見栄えは良くないかもしれませんが、x と y に対する制限をより明確に述べているように思えます。

実行すると、次のようになります。

*Main> search 999 0
906609

x * x < curr906609 の平方根は 952 であるため、停止するのは本当に良い考えであることがわかります...

于 2010-12-23T00:29:32.003 に答える
0

2 つの相互再帰関数を使用して、やりたいことができると思います。

これははるかに単純な例です ( ATS のチュートリアルから引用):

implement main (argc, argv) = let
  fun loop1 (i: int): void =
    if i <= 9 then loop2 (i, i) else ()

  and loop2  (i: int, j: int): void =
    if j <= 9 then begin
      if i < j then begin
        print ", ";
        print "("; print i; print ", "; print j; print ")";
        loop2 (i, j+1)
      end
    end else begin
      print_newline ();
      loop1 (i+1)
    end
  in
    loop1 0
  end

上記のコードは、C で記述したものと非常によく似ています (同じページから引用)。

int main (int argc, char *argv[]) { int i, j ;

for (i = 0; i <= 9; i += 1) {
  for (j = i; j <= 9; j += 1) {
    if (i < j) printf (", ") ; printf ("(%i, %i)", i, j) ;
  } /* for */
  printf ("\n") ;
} /* for */

return 0 ;

}

ご覧のとおり、ネストされたループは相互に再帰的な関数になります。可変変数 i と j は帰納変数になります。loop1 は外側のループに対応し、loop2 は内側のループに対応します。

于 2011-01-26T14:46:15.437 に答える
0

stephen tetleyのコメントで指摘されているように、FP では、継続渡しスタイルを使用して複雑な制御フローを処理できます (Contモナドに加えcallCCてbreak. ... またはgoto、CPS の乱用はかなり理解できないコードにつながる可能性があります。以下の例):

import Control.Monad.Cont

pal n = sn == reverse sn
    where sn = show n

range = [99999,99998..10000]

mfoldM a r f = foldM f a r  

curmaxm = (`runCont` id) $ mfoldM 0 range $ \m i ->
            callCC $ \break ->
                mfoldM m range $ \m j -> do
                  let ij = i*j
                  if ij < m
                     then break m
                     else return $
                          if pal ij then ij else m

2 つの mfoldM (引数が再配置された標準的な foldM) は、元のサンプルの 2 つのループに対応し、break関数引数は「内側のループ」で使用されて一度終了します (i*j > 現在の最大) 条件に違反しています (現在のその「内部ループ」の結果としての最大）。ここでは、たった 1 つの「ループ レベル」から脱出する必要があるため、ここでの callCC は間違いなくやり過ぎです。

同じロジックをfind(+ Haskell の遅延) で実装することもできます。

import Data.List
import Data.Maybe
import Control.Monad

curmax = fromJust $ foldM it 0 range
    where 
      it m i = (find pal . takeWhile (>m) . map (*i) $ range) `mplus` return m

find palここでは、最初の回文数 (これは takeWhile の (>m) 条件を満たす) または Nothing (MonadPlus のゼロ) のいずれかを返し、(または Alternatice.<|>) の後mplus(または Alternatice.<|>)itは新しい最大回文数または以前の最大回文数 (returnメートル）。最初の条件を満たす要素が見つかると検索を停止するためfind、このコードはその命令型curmaxアナログとまったく同じように動作します。どちらのバージョンも [99999..10000] の範囲で 0.5 秒で実行されます。

更新： 楽しみのために：同じアプローチですが、StateT Integer (Cont Integer) ()- Cont を使用して「ループ」から脱出し、 State を使用して最大回文を渡します（さらにforM_andを使用する機能when）。同じ効率:

import Control.Monad.Cont
import Control.Monad.State.Strict

solcs = runCont (execStateT comp 0) id
    where   
      comp = forM_ range $ \i -> callCC $ \break ->
                forM_ range $ \j -> do
                  let ij = i*j
                  m <- get
                  when (ij < m) (break ())
                  when (pal ij) (put ij)
于 2010-12-23T07:16:59.540 に答える