myInits (と myTails)

IO () さんから無限リストに対応できてない,と指摘を受けた myInits。これもできたと思う。

 cf. id:takatoh:20060513:exercise

昨日のは length を使って結果のリストの長さを決めてしまったのがいけなかった。これじゃ無限リストには対応できない。で,はじめは下の myTails と同様の考えで foldl を使って

myInits = foldl (\a b -> a ++ [last a ++ [b]]) [[]]

こうしたんだけど,やっぱり無限リストには対応できなかった。last を使ってるのがいけないのかな。
結局 zipWith を使った。

myInits xs = [] : zipWith (\a b -> a ++ [b]) (myInits xs) xs

これなら無限リストにも対応できるはずだし,zipWith はリストの終わりがくれば止まってくれる。さて,試してみよう。

*Main> myInits "abcde"
["","a","ab","abc","abcd","abcde"]
*Main> myInits ""
[""]
*Main> take 10 $ myInits [1..]
[[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3
,4,5,6,7,8],[1,2,3,4,5,6,7,8,9]]

よし,これならOK。ちゃんと無限リストに対応できてるし,先頭には空リストも付いてるな。ちなみに inits はこうだ。

Prelude List> inits "abcde"
["","a","ab","abc","abcd","abcde"]
Prelude List> inits ""
[""]
Prelude List> take 10 $ inits [1..]
[[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3
,4,5,6,7,8],[1,2,3,4,5,6,7,8,9]]

もう一つ,myTails。こっちはリストの最後に空リストがないところが違ってた。

myTails = foldr (\a b -> (a:head b):b) [[]]

結果。

*Main> myTails "abcde"
["abcde","bcde","cde","de","e",""]
*Main> myTails ""
[""]

ちなみに tails はこう。おんなじ。

Prelude List> tails "abcde"
["abcde","bcde","cde","de","e",""]
Prelude List> tails ""
[""]

OK。

カテゴリー: Haskell パーマリンク

1 Response to myInits (と myTails)

  1. IO () のコメント:

    myInits の foldl バージョンですが ”Yet Another Haskell Tutorial”
    http://hpcgi2.nifty.com/1to100pen/wiki/wiki.cgi?a=redirect&p=http://www.isi.edu/~hdaume/htut/
    3.3.2 Simple List Functions の NOTE に「However, foldr can work on infinite lists, while foldl cannot. 云々」とあります。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください