8

命令型アルゴリズムを関数型スタイルに変換するには、いくつかの困難があります。理解できない主な概念は、シーケンス内の位置に応じてシーケンスに値を入力する方法です。Haskell では、次のアルゴリズムの慣用的なソリューションはどのようになりますか?

A = unsigned char[256]
idx <- 1
for(i = 0 to 255)
    if (some_condition(i))
        A[i] <- idx
        idx++
    else
        A[i] = 0;

このアルゴリズムは基本的に、ヒストグラムのマッピング関数のルックアップ テーブルを作成します。

この種の問題をよりよく理解するのに役立つリソースを知っていますか?

4

4 に答える 4

8

関数型プログラミングの核となるアイデアの 1 つは、アルゴリズムをデータ変換として表現することです。Haskell のような遅延言語では、さらに一歩進んで、遅延データ構造を具体化された計算と考えることができます。非常に現実的な意味で、Haskell のリストは通常​​のリンクされたリストよりもループに似ています: それらは段階的に計算でき、一度にメモリに存在する必要はありません。同時に、データ型を渡してパターン マッチングで検査する機能のようなデータ型を持つことの多くの利点も得られます。

これを念頭に置いて、インデックスを使用して for ループを表現するための「トリック」は、取り得るすべての値のリストを作成することです。あなたの例はおそらく最も単純なケースです:からまでiのすべての値を取るので、Haskell の組み込み表記を範囲に使用できます:0255

[0..255]

大まかに言うと、これは Haskell のfor (i = 0 to 255);に相当するものです。次に、再帰関数または標準ライブラリの高階関数のいずれかによってこのリストをトラバースすることにより、ループ内の実際のロジックを実行できます。(2 番目のオプションを強くお勧めします。)

この特定のロジックは、fold. 折り畳みにより、リスト項目を項目ごとに取り込んで、何らかの結果を構築できます。各ステップで、リスト項目と、これまでに構築された結果の値を取得します。この特定のケースでは、インデックスをインクリメントしながら左から右にリストを処理したいので、foldl;を使用できます。1 つのトリッキーな部分は、リストが逆向きに生成されることです。

のタイプは次のfoldlとおりです。

foldl :: (b -> a -> b) -> b -> [a] -> b

したがって、関数は中間値とリスト要素を受け取り、更新された中間値を生成します。リストを作成してインデックスを追跡しているため、中間値は両方を含むペアになります。次に、最終結果が得られたら、idx値を無視して、取得した最終リストを逆にすることができます。

a = let (result, _) = foldl step ([], 1) [0..255] in reverse result
  where step (a, idx) i
          | someCondition i = (idx:a, idx + 1)
          | otherwise       = (0:a, idx)

実際、何らかの中間状態 (この場合) を追跡しながらリストを変換するパターンはidx、型に関して独自の機能を持つほど一般的Stateです。コアの抽象化はもう少し複雑です (["You Could Have Invented Monads"][you] を読んで素晴らしい紹介を読んでください) が、結果として得られるコードは実際には非常に読みやすくなっています (インポートを除いて、私は推測します:P) :

import Control.Applicative
import Control.Monad 
import Control.Monad.State

a = evalState (mapM step [0..255]) 1
  where step i
          | someCondition i = get <* modify (+ 1)
          | otherwise       = return 0

バックグラウンド[0..255]で何らかの状態 ( の値) を追跡しながらマッピングするという考え方です。すべての配管をまとめて最終結果を得る方法です。関数は各入力リスト要素に適用され、状態にアクセスまたは変更することもできます。idxevalStatestep

関数の最初のケースstepは興味深いものです。<*演算子は、最初に左の処理を実行し、次に右の処理を実行するように指示しますが、左の値を返します。これにより、現在の状態を取得してインクリメントしますが、インクリメントする前に取得した値を返すことができます。私たちの状態の概念は第一級のエンティティであり、次のようなライブラリ関数を持つことができるという事実<*は非常に強力です。この特定のイディオムはツリーをトラバースするのに非常に役立ち、他の同様のイディオムは他のコードに非常に役立ちます。

于 2015-03-27T18:25:21.443 に答える
3

使用するデータ構造に応じて、この問題にアプローチする方法がいくつかあります。最も単純なものは、おそらくリストと で利用可能な基本的な機能ですPrelude:

a = go 1 [] [0..255]
    where
        go idx out [] = out
        go idx out (i:is) =
            if condition i
                then go (idx + 1) (out ++ [idx]) is
                else go idx (out ++ [0]) is

これは、2 つのアキュムレータidxおよびoutでワーカー パターンを使用し、要素がなくなるまで最後のパラメーターをたどり、 を返しますout。foldこれは確かにある種の に変換できますが、いずれにしてもあまり効率的ではありません。リストに項目を追加するの++は非常に非効率的です。idx : outと0 : outを使用reverseしてから の出力を使用することで改善できますがgo、それでも理想的な解決策ではありません。

別の解決策は、Stateモナドを使用することです。

a = flip runState 1 $ forM [0..255] $ \i -> do
        idx <- get
        if condition i
            then do
                put $ idx + 1    -- idx++
                return idx       -- A[i] = idx
            else return 0

これは確かにはるかに不可欠に見えます。1inは、flip runState 1初期状態が であることを示しておりidx = 1、次にforM(for ループのように見えますが実際にはそうではありません) overを使用し[0..255]、ループ変数はiであり、残りのロジックを実装するだけです。

もっと高度にしたい場合は、StateTおよびSTモナドを使用して、同時に状態を持つ実際の可変配列を持つことができます。ただし、これがどのように機能するかの説明は、この回答の範囲をはるかに超えています。

import Control.Monad.State
import Control.Monad.ST
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV


a :: V.Vector Int
a = runST $ (V.freeze =<<) $ flip evalStateT (1 :: Int) $ do
    a' <- lift $ MV.new 256
    lift $ MV.set a' 0
    forM_ [0..255] $ \i -> do
        when (condition i) $ do
            idx <- get
            lift $ MV.write a' i idx
            put $ idx + 1
    return a'

各要素が最初から に設定されるように少し単純化しました。現在のインデックスが条件を満たしている場合は、ループ オーバー0の初期状態から始めて、現在のインデックスを取得し、それを現在のインデックスに書き込み、インクリメントします。これをステートフル操作として実行し、ベクトルをフリーズして、最後にモナド側を実行します。これにより、実際の変更可能なベクトルをモナド内に安全に隠すことができるため、計算するためにかなり奇妙なことをしなければならないことを外の世界は知りません。idx = 1[0..255]iidxidxSTSTa

于 2015-03-27T18:17:30.153 に答える
1

明示的な再帰:

a = go 0 1
  where go 256 _   = []
        go i   idx | someCondition i = idx : go (i+1) (idx+1)
                   | otherwise       = 0   : go (i+1) idx

展開: (上記の明示的な再帰のバリアント)

a = unfoldr f (0,1)
    where f (256,_) = Nothing
          f (i,idx) | someCondition i = Just (idx,(i+1,idx+1))
                    | otherwise       = Just (0  ,(i+1,idx  ))
于 2015-03-27T18:20:04.627 に答える
0

通常、ループはさまざまなfold関数を使用して表現できます。これを使用するソリューションは次のとおりです（ stackoverflowエラーが発生した場合にfoldl切り替えることができます）：foldl'

f :: (Num a) => (b -> Bool) -> a -> [b] -> [a]
f pred startVal = reverse . fst . foldl step ([], startVal)
    where            
        step (xs, curVal) x 
            | pred x = (curVal:xs, curVal + 1)
            | otherwise = (0:xs, curVal)

それの使い方？この関数は述語 (someConditionコード内)、インデックスの初期値、反復する要素のリストを受け取ります。つまりf someCondition 1 [0..255]、質問から例の結果を取得するために呼び出すことができます。

于 2015-03-27T18:10:27.520 に答える