3

以下のコードは、指定された整数 n に対して、リストの最初の n 個の項目を保持し、次の n 個の項目を削除し、次の n 個を保持する、というように続きます。これは、任意の有限リストに対して正しく機能します。

無限リストで使用できるようにするために、「seq」演算子を使用して、例として「foldl」のように再帰ステップの前にアキュムレータの評価を強制しました。

アキュムレータの値をトレースしてテストしたところ、有限リストで必要に応じて効果的に計算されているようです。

ただし、無限リストに適用すると機能しません。メイン関数の「取得」は、内部計算が終了した後にのみ実行されます。もちろん、これは無限リストでは決して起こりません。

誰かが私の間違いを教えてもらえますか?

main :: IO ()
main = print (take 2 (foo 2 [1..100]))

foo :: Show a => Int -> [a] -> [a]
foo l lst = inFoo keepOrNot 1 l lst []

inFoo :: Show a => (Bool -> Int -> [a] -> [a] -> [a]) -> Int -> Int -> [a] -> [a] -> [a]
inFoo keepOrNot i l  [] lstOut  = lstOut
inFoo keepOrNot i l lstIn lstOut = let lstOut2 = (keepOrNot (odd i) l lstIn lstOut) in
                      stOut2 `seq` (inFoo keepOrNot (i+1) l (drop l lstIn) lstOut2)

keepOrNot :: Bool -> Int -> [a] -> [a] -> [a]
keepOrNot b n lst1 lst2 = case b of
  True -> lst2 ++ (take n lst1)
  False -> lst2
4

3 に答える 3

6

リスト連結の実装方法は次のとおりです。

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

ご了承ください

  • 右側のリスト構造はそのまま再利用されます（まだ評価されていなくても、怠惰です）
  • 左側のリスト構造が書き換えられます (コピーされます)

これは、 を使用++してリストを作成する場合、アキュムレータを右側に配置する必要があることを意味します。(有限リストの場合、単に効率上の理由から --- アキュムレータが左側にある場合、繰り返しコピーされ、これは非効率的です。無限リストの場合、呼び出し元は結果の最初の要素を見ることができません。これは最後にコピーされたものであり、アキュムレータの右側に連結するものが常に他にあるため、最後にはありません。)

のTrue場合、keepOrNotの左側にアキュムレータがあり++ます。別のデータ構造を使用する必要があります。

この場合の通常のイディオムは、差分リストを使用することです。[a]アキュムレータにtype を使用する代わりに、 を使用します[a] -> [a]。アキュムレータは、入力として与えられたリストにリストを追加する関数になりました。これにより、コピーの繰り返しが回避され、リストを遅延して構築できます。

keepOrNot :: Bool -> Int -> [a] -> ([a] -> [a]) -> ([a] -> [a])
keepOrNot b n lst1 acc = case b of
  True -> acc . (take n lst1 ++)
  False -> acc

アキュムレータの初期値は ですid。これを従来のリストに変換したい場合は、[](つまり、acc []) で呼び出します。

seqここでは赤いニシンです。seqリスト全体を強制するわけではありません。またはseqの形式であるかどうかのみを判別します。[]x : xs

Haskell を学んでいますね。したがって、差分リスト アキュムレータを使用するようにコードを変更することは、演習としては良い考えです。無限リストを使用すると、コードの別の部分でやけどをする可能性があります。知らない。

しかし、もっと良い書き方がありfooます。

foo c xs = map snd . filter fst . zipWith f [0..] $ xs
  where f i x = (even (i `div` c), x)
于 2012-10-23T08:49:25.813 に答える
3

したがって、リストをn要素のグループにグループ化し、他のすべてのグループを削除する必要があります。これを直接書き留めることができます。

import Data.List (unfoldr)

groups n xs = takeWhile (not.null) $ unfoldr (Just . splitAt n) xs

foo c xs = concatMap head . groups 2 . groups c $ xs

dave4420はすでにコードの何が問題になっているのかを説明していますが、IMOがどのようにしてそこに到達したかについてコメントしたいと思います。あなたのkeepOrNot :: Bool -> Int -> [a] -> [a] -> [a]機能は一般的すぎます。Bool受信した、任意の Bool;に従って動作します。しかし、あなたはそれに交互の価値観の連続を与えることを知っています。関数を使用したプログラミングは、パイプをじょうごに差し込むようなものです。ある関数の出力が次の関数への入力として機能します。ここではじょうごが広すぎるため、接触が緩んでいます。TrueFalse

これらの行に沿ったコードの最小限の書き直しは、

foo n lst = go lst
  where
    go lst = let (a,b) = splitAt n lst
                 (c,d) = splitAt n b
             in
                 a ++ go d

接触は「タイト」で、ここでは「情報漏えい」はありません。このコードでは、自分で2回 （*）作業を行い、明示的に「パイプを接続」して、一方の結果（）を取得し、もう一方の結果（a）を削除しcます。

--
（*） 2回、2つのブール値を反映し、、、Trueを単純な方法で次々Falseに交互に表示します。したがって、これはコードの構造に固定されてキャプチャされ、任意のブール値に対応できるパラメータとしてぶら下がることはありません。

于 2012-10-23T10:05:14.267 に答える
1

(++)dava4420 が言ったように、左から蓄積するために使用するべきではありません。しかし、おそらくあなたはまったく蓄積すべきではありません! Haskell では、遅延により、Lisp などで使用する必要がある末尾再帰よりも、単純な「ヘッド構築」が多くの場合より効率的になります。例えば：

foo :: Int -> [a] -> [a]     -- why would you give this a Show constraint?
foo ℓ = foo' True
  where foo' _ [] = []
        foo' keep lst
          | keep       = firstℓ ++ foo' False other
          | otherwise  =           foo' True other
         where (firstℓ, other) = splitAt ℓ lst
于 2012-10-23T10:16:20.663 に答える