1

実行時にファイルから読み取られ、次のようなタプルで表されるデータのリストがあります。

[(1,0.1),(2,0.2),(3,0.3)...etc...]

そして、リストと 2 つの整数をパラメーターとして取り、double を返す関数を作成しました。

f :: [(Int,Double)] -> Int -> Int -> Double
f mylist i j
    | j < n = (do some stuff)
    | otherwise = max (f mylist (i-1) j) (some other stuff with m_i and p_i)
    where m_i = fst $ mylist !! (i-1)
          p_i = snd $ mylist !! (i-1)

さて、私は Haskell と純粋な関数の概念に慣れていませんが、リストは静的であるため (変更されません)、リストを関数に渡す必要があるかどうか疑問に思っています。

大量の再帰層を介して大きなリストを渡すのは悪い習慣ですか?

実行時にリストを読んだ場合、2 つの関数を「設定」mしpて、このように使用できますか?

f :: Int -> Int -> Double
f i j
    | j < n = (do some stuff)
    | otherwise = max (f (i-1) j) (some other stuff with m_i and p_i)
    where m_i = m (i-1)
          p_i = p (i-1)

もしそうなら、実行時にファイルから読み取った値を基本的に返すように関数mと関数（純粋ですよね？）を設定するにはどうすればよいですか（私が正しく理解していれば、これは純粋ではありません）。p

助けてくれてありがとう！

4

5 に答える 5

4

いくつかの落とし穴はありますが、大きなリストを再帰することは悪い習慣ではありません。一般に、再帰関数が段階的に生産的である限り、O(1) memory, O(n) time非常に大きなリストでも問題ありません ( )。

あなたの場合、インデックス値が下向きに再帰するため、リストを逆方向に読んでいるようです。これは、リストを反転するには、リスト全体をメモリにロードする必要があることを意味します。

ファイルから読み込んでいる場合、ほぼ間違いなく impureです。純粋な操作であるかのように振る舞うことが価値がある場合もありますが、通常は、IO ベースの初期セットアップ/構成手順にこのようなことを渡す方が適切です。

たとえば、私の実行可能ファイルは次のようになります

main :: IO ()
main = do bigList <- readFileSomehow -- this is impure
          let res = f bigList        -- this is pure
          print res                  -- this is impure again

ここでは、構文を使用して、最初のステップとして、不純なファイル読み取りからdoを抽出しています。bigList :: [(Int, Double)]次に、それをすぐbigListに純粋な関数に渡しf、純粋な結果を取得しresます。最後に、純粋な に対して不純なprintアクションを実行しresます。

これにより、すべての不純物をmain関数に分離しf、最初にその大きな入力に到達した「方法」などの不純な詳細から完全に独立して記述することができます。

m説明した関数と関数を使用して、このリストの概念をさらに抽象化することができpます。彼らがしているのは、リストを隠して 経由でのみアクセスできるようにすることだけ(!!)です。

inner :: Int -> Int -> (Int -> Int) -> (Int -> Double) -> Something

outer :: [(Int, Double)] -> Int -> Int -> Something
outer bigList i j = inner i j (\ix -> fst $ bigList !! ix) (\ix -> snd $ bigList !! ix)

どこでouter「ラップ」し、これらの 2 つのインデックス関数を介して以外はinner表示されないようにします。bigList

最後に、残念ながら、このメソッド全体には、それほど「Haskelly」な感じはありません。大きなリストで使用する明示的な再帰(!!)は、速度低下とコードの重複につながる傾向があります。可能であれば、 maps とs の観点から意図を定式化することをお勧めします。foldr

于 2013-09-25T19:37:46.853 に答える
3

大量の再帰層を介して大きなリストを渡すのは悪い習慣ですか?

概念的には、そうではない大きなリストのコピーを作成することを心配しているようですが、Haskell は再帰を通じて同じデータ構造に対処します。明示的に持ち上げる必要はありません。

explicit を使用(!!)すると、いくつかの問題が発生する可能性があります。データの線形スイープを行っているため、問題をマップまたはフォールド、またはそれらの組み合わせとして表現してみる価値があるかもしれません。それができれば、コンパイラに対して多くの最適化を行うことができます。

また、図書館を調べることを強くお勧めしvectorます。

http://hackage.haskell.org/package/vector-0.10.0.1

于 2013-09-25T19:34:50.210 に答える
1

はい、リストは不変ですが、コンパイル時にはわかりません。だからあなたには2つの選択肢があります

  1. リストを渡す
  2. このリストを認識し、インデックスでその値を提供する関数を渡します

これらは概念的に同等であることに注意してください。どちらも、値のリストを表すデータを渡す必要があります。これは、それをどのように表すかの問題です。

だからp、m次のようになります

 myList = ...
 p i = fst $ myList !! i
 m i = fst $ myList !! i

それは本当にあなたをあまり買わない.

気分が良くなる場合は、10000 個の要素のリストを関数に渡す (作成しない) のに、3 個のリストと同じコストがかかります。これは、head + 残りへのポインターまたは nil 値のいずれかにコンパイルされます。これは、Haskell が単独でリンクされたリストを持っているためです。

List a = Cons a (List a) -- Head, rest of list
       | Nil             -- End of list

したがって、値渡しは命令型配列に比べて安価ですが、ルックアップ時間はそれに応じて低下します。

これに対する当然の結果として、それには非常に注意して(!!)ください。あなたの問題は折り目と地図のどちらで表現するのが適切かを検討してください。高階コンビネータの使用は非常に Haskelly です :)

于 2013-09-25T19:34:43.860 に答える
1

1つのリストに2つの関数を使用する方法 -mapたとえば、タプルを使用して作成する

result :: (a->b) -> (a->c) -> [a] -> [(b,c)]
result m p = map (\elem -> (f elem , p elem) )  list

リストをパラメーターとして渡す場合 - 悪いことではありません。使用しない場合、コンパイラーによって読み取られません。しかし、アルゴリズムの複雑さは重要です。

于 2013-09-25T19:37:16.053 に答える