- 関数型プログラミング言語Haskell Part26
934 ：デフォルトの名無しさん[]：2015/01/05(月) 13:54:22.37 ID:UJnBa08N - >>929
リスト走査を1度ですませたいなら融合変換すればよいのでは．
|
- 関数型プログラミング言語Haskell Part26
942 ：デフォルトの名無しさん[]：2015/01/05(月) 15:59:36.20 ID:UJnBa08N - >>937
zipで一回，filterで一回，計2回ではないでしょうか？
|
- 関数型プログラミング言語Haskell Part26
944 ：デフォルトの名無しさん[]：2015/01/05(月) 16:29:22.31 ID:UJnBa08N - >>943
中間リストがなくなればその分の走査が減るとおもいます．
|
- 関数型プログラミング言語Haskell Part26
947 ：デフォルトの名無しさん[]：2015/01/05(月) 18:31:50.63 ID:UJnBa08N - >>946
oddElems :: [a] -> [a]
oddElems = filter' snd (odd . fst) . zip [0..]
filter' _ _ [] = []
filter' f p (x:xs) = if p x then f x : filter' f p xs
このとき，oddElem の入力となるリストを es．その長さを n = length es とします．
zip [0..] は関数で，この関数が結果のリスト全体を作成するには es の全要素を辿ります.
zip [0..] es が生成するリストを es' とすると，そのは長さは es の長さと同じ n です．
filter' snd (odd . fst) es' は結果のリスト全体を生成するのに es の全要素を辿ります．
融合変換して es' という中間リストがなくなれば，辿るべきリストが1つ減っていることが期待できますよね．
|
- 関数型プログラミング言語Haskell Part26
948 ：デフォルトの名無しさん[]：2015/01/05(月) 18:48:33.68 ID:UJnBa08N - 訂正 es → es'
filter' snd (odd . fst) es' は結果のリスト全体を生成するのに es' の全要素を辿ります．
|
- 関数型プログラミング言語Haskell Part26
949 ：デフォルトの名無しさん[]：2015/01/05(月) 18:49:41.11 ID:UJnBa08N - 中間リストといっているのはzip [0..] が生成するリストのことです．
|
- 関数型プログラミング言語Haskell Part26
951 ：デフォルトの名無しさん[]：2015/01/05(月) 19:47:30.17 ID:UJnBa08N - 走査という曖昧な言葉をつかったのが失敗でした．
中間リストの生成を除去するといえばよかったですね．
|
- 関数型プログラミング言語Haskell Part26
952 ：デフォルトの名無しさん[]：2015/01/05(月) 20:19:28.54 ID:UJnBa08N - oddElems :: [a] -> [a]
oddElems = filter' snd (odd . fst) . zip [0..]
filter' snd (odd . fst) . zip [0..]
⇔ { zipp = uncurry zip とする }
filter' snd (odd . fst) . zipp . (,) [0..]
⇔ { addifodd (i,x) xs = if odd i then x:xs eles xs とする }
foldr addifodd [] . zipp . (,) [0..]
⇔ { phipair (xxs,yys) = if null xxs || null yys then Nothing else Just ((head xxs,head yys),(tail xxs, tail yys)) とする }
foldr addifodd [] . unfoldr phipair . (,) [0..]
⇔ { hylo f e phi x = case phi x of {Nothing -> e; Just (y,z) -> f y (hylo f e phi z)} とする }
hylo addifodd [] phipair . (,) [0..]
まちがえてなければ，これで融合変換できたことになると思います．
oddelems = hylo addifodd [] phipair . (,) [0..]
|