The Haskell 98 Report
top | back | next | contents | function index
module List ( elemIndex, elemIndices, find, findIndex, findIndices, nub, nubBy, delete, deleteBy, (\\), deleteFirstsBy, union, unionBy, intersect, intersectBy, intersperse, transpose, partition, group, groupBy, inits, tails, isPrefixOf, isSuffixOf, mapAccumL, mapAccumR, sort, sortBy, insert, insertBy, maximumBy, minimumBy, genericLength, genericTake, genericDrop, genericSplitAt, genericIndex, genericReplicate, zip4, zip5, zip6, zip7, zipWith4, zipWith5, zipWith6, zipWith7, unzip4, unzip5, unzip6, unzip7, unfoldr, -- ...and what the Prelude exports -- []((:), []), -- This is built-in syntax map, (++), concat, filter, head, last, tail, init, null, length, (!!), foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1, iterate, repeat, replicate, cycle, take, drop, splitAt, takeWhile, dropWhile, span, break, lines, words, unlines, unwords, reverse, and, or, any, all, elem, notElem, lookup, sum, product, maximum, minimum, concatMap, zip, zip3, zipWith, zipWith3, unzip, unzip3 ) where infix 5 \\ elemIndex :: Eq a => a -> [a] -> Maybe Int elemIndices :: Eq a => a -> [a] -> [Int] find :: (a -> Bool) -> [a] -> Maybe a findIndex :: (a -> Bool) -> [a] -> Maybe Int findIndices :: (a -> Bool) -> [a] -> [Int] nub :: Eq a => [a] -> [a] nubBy :: (a -> a -> Bool) -> [a] -> [a] delete :: Eq a => a -> [a] -> [a] deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a] (\\) :: Eq a => [a] -> [a] -> [a] deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] union :: Eq a => [a] -> [a] -> [a] unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] |
intersect :: Eq a => [a] -> [a] -> [a] intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] intersperse :: a -> [a] -> [a] transpose :: [[a]] -> [[a]] partition :: (a -> Bool) -> [a] -> ([a],[a]) group :: Eq a => [a] -> [[a]] groupBy :: (a -> a -> Bool) -> [a] -> [[a]] inits :: [a] -> [[a]] tails :: [a] -> [[a]] isPrefixOf :: Eq a => [a] -> [a] -> Bool isSuffixOf :: Eq a => [a] -> [a] -> Bool mapAccumL :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c]) mapAccumR :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c]) unfoldr :: (b -> Maybe (a,b)) -> b -> [a] sort :: Ord a => [a] -> [a] sortBy :: (a -> a -> Ordering) -> [a] -> [a] insert :: Ord a => a -> [a] -> [a] insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a] maximumBy :: (a -> a -> Ordering) -> [a] -> a minimumBy :: (a -> a -> Ordering) -> [a] -> a genericLength :: Integral a => [b] -> a genericTake :: Integral a => a -> [b] -> [b] genericDrop :: Integral a => a -> [b] -> [b] genericSplitAt :: Integral a => a -> [b] -> ([b],[b]) genericIndex :: Integral a => [b] -> a -> b genericReplicate :: Integral a => a -> b -> [b] zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)] zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)] zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [(a,b,c,d,e,f)] zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] -> [(a,b,c,d,e,f,g)] zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e] zipWith5 :: (a->b->c->d->e->f) -> [a]->[b]->[c]->[d]->[e]->[f] zipWith6 :: (a->b->c->d->e->f->g) -> [a]->[b]->[c]->[d]->[e]->[f]->[g] zipWith7 :: (a->b->c->d->e->f->g->h) -> [a]->[b]->[c]->[d]->[e]->[f]->[g]->[h] unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d]) unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e]) unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f]) unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g]) |
このライブラリはリスト上のあまり使用頻度の高くない演算を定義している。
elemIndex val list は、もしあれば、 list 中で最初にあらわれた val のインデックスを Just index として返す。 not (val `elem` list) であれば、 Nothing を返す。
elemIndices val list は list 中にあらわれる val の出現に対応する インデックスをその順にならべたリストを返す。
List 型上の「集合」演算がいくつも定義されています。 nub (「エッセンス」の意)はリストから重複する要素を取り除く。 delete、(\\)、union および intersect は第一引数として重複のないリストが与えられたら、 重複要素をもたないという不変表明を保持する。
nub はリストのから要素の重複をとりのぞく。たとえば、
nub [1,3,1,4,3,3] = [1,3,4]
delete x はそのリスト引数から最初に出現した
x を取り除く。たとえば、
delete 'a' "banana" == "bnana"
(\\) はリストの差(結合性はない)である。 xs \\ ys の結果は、xs のなかから ys の各要素の最初に出現したものを取り除いた残りである。し たがって、 (xs ++ ys) \\ xs == ys である。
union はリストの和である。すなわち、
"dog" `union` "cow" == "dogcw"
である。
intersect はリストの共通部分である。すなわち、
[1,2,3,4] `intersect` [2,4,6,8] == [2,4]
である。
intersperse sep はそのリスト引数の要素の間に
seq を挿入したものである。すなわち、
intersperse ',' "abcde" == "a,b,c,d,e"
である。
transpose はその引数の行と列を入れ替える。すなわち、
transpose [[1,2,3],[4,5,6]] == [[1,4],[2,5],[3,6]]
である。
partition は一つの述語と一つのリストをとり、リストの対を
返す。それぞれの結果のリストの一方は引数リスト要素のうち述語を
満す要素をもつもの、一方は満さないものである。すなわち、
partition p xs == (filter p xs, filter (not . p) xs)
である。
sort/sortBy は安定した整列アルゴリズムの 実装である。insertBy 関数はリストへ指定した順序関係に したがってオブジェクトを挿入する。
insert は新しい要素を順序リスト(昇順にならんでいるもの) に挿入する。
group はその引数であるリストを等しい隣接要素のリストの
リストに分解する。たとえば、
group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
である。
inits は引数のリストの先頭部分列の短いほうから順に
ならべたリストを返す。
inits "abc" == ["","a","ab","abc"]
tails は引数のリストの末尾部分列を長いほうから順に
ならべたリストを返す。
tails "abc" == ["abc", "bc", "c",""]
mapAccumL f s l は f を蓄積「状態」 パラメータ s と l の各要素に順に適用する。
mapAccumR はリストを左から右へではなく、右から左へ辿る という点をのぞけば mapAccumL と同じである。
unfoldr 関数は foldr と「双対」な関数である。
foldr はリストを畳み込んで一つの要約値にするが、
unfoldr は種値からリストを構築する。たとえば、
iterate f == unfoldr (\x -> Just (x, f x))
以下の条件が成り立つ場合
f' (f x y) = Just (x,y)
f' z = Nothing
unfoldr は foldr 演算をとりけすことが可能である。
unfoldr f' (foldr f z xs) == xs
isPrefixOf と isSuffixOf は第一引数が第二引数の それぞれ接頭辞、接尾辞になっているかどうかを判定する。
慣例でいうと、多重定義関数には、"By" 接尾辞のついた、
非多重定義関数版がある。例えば、関数 nub は以下のように
定義されている。
nub :: (Eq a) => [a] -> [a]
nub [] = []
nub (x:xs) = x : nub (filter (\y -> not (x == y)) xs)
しかし、同等性メソッドはすべての状況で適切であるとは限らない。
次の関数
nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy eq [] = []
nubBy eq (x:xs) = x : nubBy eq (filter (\y -> not (eq x y)) xs)
ではプログラマが同等性テストを独自に与えることができる。
"By" 関数が、Eq 文脈を二項述語で置き換えた場合、
この述語は同等性を定義するものと仮定される。"By" 関数が
Ord 文脈を二項述語で置き換えた場合、この述語は全順序を
定義しているものと見なす。
"By" の変形は以下のようなものがある。 nubBy、deleteBy、deleteFirstBy (\\ の By バージョン)、unionBy、 intersectBy、groupBy、sortBy、 insertBy、maximumBy、minimumBy。
このライブラリには elemBy はない。それは、 any (eq x) が elemBy eq x するだろう仕事と同じことをするからである。手の込んだ多重定義関数 (elemIndex, elemIndices, isPrefixOf, isSuffixOf) は "By" の変形とするほどには 重要でないと考えられた。
接頭辞 "generic" は Prelude の関数の多重定義された
総称版であることを示している。たとえば、
genericLength :: Integral a => [b] -> a
は length の総称版である。
"generic" 演算には以下のようなものがある。 genericLength、genericTake、genericDrop、 genericSplitAt、genericIndex (!! の総称版)、 genericReplicate
プレリュードでは、zip、zip3、unzip、 unzip3、zipWith、zipWith3 が用意されている。 このリストライブラリでは同様の 3 種の演算が 4、5、6、7 の引数に対して 用意されている。
module List (
elemIndex, elemIndices,
find, findIndex, findIndices,
nub, nubBy, delete, deleteBy, (\\), deleteFirstsBy,
union, unionBy, intersect, intersectBy,
intersperse, transpose, partition, group, groupBy,
inits, tails, isPrefixOf, isSuffixOf,
mapAccumL, mapAccumR,
sort, sortBy, insert, insertBy, maximumBy, minimumBy,
genericLength, genericTake, genericDrop,
genericSplitAt, genericIndex, genericReplicate,
zip4, zip5, zip6, zip7,
zipWith4, zipWith5, zipWith6, zipWith7,
unzip4, unzip5, unzip6, unzip7, unfoldr,
-- ...and what the Prelude exports
-- []((:), []),
-- This is built-in syntax
map, (++), concat, filter,
head, last, tail, init, null, length, (!!),
foldl, foldl1, scanl, scanl1, foldr, foldr1, scanr, scanr1,
iterate, repeat, replicate, cycle,
take, drop, splitAt, takeWhile, dropWhile, span, break,
lines, words, unlines, unwords, reverse, and, or,
any, all, elem, notElem, lookup,
sum, product, maximum, minimum, concatMap,
zip, zip3, zipWith, zipWith3, unzip, unzip3
) where
import Maybe( listToMaybe )
infix 5 \\
elemIndex :: Eq a => a -> [a] -> Maybe Int
elemIndex x = findIndex (x ==)
elemIndices :: Eq a => a -> [a] -> [Int]
elemIndices x = findIndices (x ==)
find :: (a -> Bool) -> [a] -> Maybe a
find p = listToMaybe . filter p
findIndex :: (a -> Bool) -> [a] -> Maybe Int
findIndex p = listToMaybe . findIndices p
findIndices :: (a -> Bool) -> [a] -> [Int]
findIndices p xs = [ i | (x,i) <- zip xs [0..], p x ]
nub :: Eq a => [a] -> [a]
nub = nubBy (==)
nubBy :: (a -> a -> Bool) -> [a] -> [a]
nubBy eq [] = []
nubBy eq (x:xs) = x : nubBy eq (filter (\y -> not (eq x y)) xs)
delete :: Eq a => a -> [a] -> [a]
delete = deleteBy (==)
deleteBy :: (a -> a -> Bool) -> a -> [a] -> [a]
deleteBy eq x [] = []
deleteBy eq x (y:ys) = if x `eq` y then ys else y : deleteBy eq x ys
(\\) :: Eq a => [a] -> [a] -> [a]
(\\) = foldl (flip delete)
deleteFirstsBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
deleteFirstsBy eq = foldl (flip (deleteBy eq))
union :: Eq a => [a] -> [a] -> [a]
union = unionBy (==)
unionBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
unionBy eq xs ys = xs ++ deleteFirstsBy eq (nubBy eq ys) xs
intersect :: Eq a => [a] -> [a] -> [a]
intersect = intersectBy (==)
intersectBy :: (a -> a -> Bool) -> [a] -> [a] -> [a]
intersectBy eq xs ys = [x | x <- xs, any (eq x) ys]
intersperse :: a -> [a] -> [a]
intersperse sep [] = []
intersperse sep [x] = [x]
intersperse sep (x:xs) = x : sep : intersperse sep xs
-- transpose is lazy in both rows and columns,
-- and works for non-rectangular 'matrices'
-- For example, transpose [[1,2],[3,4,5],[]] = [[1,3],[2,4],[5]]
-- Note that [h | (h:t) <- xss] is not the same as (map head xss)
-- because the former discards empty sublists inside xss
transpose :: [[a]] -> [[a]]
transpose [] = []
transpose ([] : xss) = transpose xss
transpose ((x:xs) : xss) = (x : [h | (h:t) <- xss]) :
transpose (xs : [t | (h:t) <- xss])
partition :: (a -> Bool) -> [a] -> ([a],[a])
partition p xs = (filter p xs, filter (not . p) xs)
-- group splits its list argument into a list of lists of equal, adjacent
-- elements. e.g.,
-- group "Mississippi" == ["M","i","ss","i","ss","i","pp","i"]
group :: Eq a => [a] -> [[a]]
group = groupBy (==)
groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy eq [] = []
groupBy eq (x:xs) = (x:ys) : groupBy eq zs
where (ys,zs) = span (eq x) xs
-- inits xs returns the list of initial segments of xs, shortest first.
-- e.g., inits "abc" == ["","a","ab","abc"]
inits :: [a] -> [[a]]
inits [] = [[]]
inits (x:xs) = [[]] ++ map (x:) (inits xs)
-- tails xs returns the list of all final segments of xs, longest first.
-- e.g., tails "abc" == ["abc", "bc", "c",""]
tails :: [a] -> [[a]]
tails [] = [[]]
tails xxs@(_:xs) = xxs : tails xs
isPrefixOf :: Eq a => [a] -> [a] -> Bool
isPrefixOf [] _ = True
isPrefixOf _ [] = False
isPrefixOf (x:xs) (y:ys) = x == y && isPrefixOf xs ys
isSuffixOf :: Eq a => [a] -> [a] -> Bool
isSuffixOf x y = reverse x `isPrefixOf` reverse y
mapAccumL :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
mapAccumL f s [] = (s, [])
mapAccumL f s (x:xs) = (s'',y:ys)
where (s', y ) = f s x
(s'',ys) = mapAccumL f s' xs
mapAccumR :: (a -> b -> (a, c)) -> a -> [b] -> (a, [c])
mapAccumR f s [] = (s, [])
mapAccumR f s (x:xs) = (s'', y:ys)
where (s'',y ) = f s' x
(s', ys) = mapAccumR f s xs
unfoldr :: (b -> Maybe (a,b)) -> b -> [a]
unfoldr f b = case f b of
Nothing -> []
Just (a,b) -> a : unfoldr f b
sort :: (Ord a) => [a] -> [a]
sort = sortBy compare
sortBy :: (a -> a -> Ordering) -> [a] -> [a]
sortBy cmp = foldr (insertBy cmp) []
insert :: (Ord a) => a -> [a] -> [a]
insert = insertBy compare
insertBy :: (a -> a -> Ordering) -> a -> [a] -> [a]
insertBy cmp x [] = [x]
insertBy cmp x ys@(y:ys')
= case cmp x y of
GT -> y : insertBy cmp x ys'
_ -> x : ys
maximumBy :: (a -> a -> Ordering) -> [a] -> a
maximumBy cmp [] = error "List.maximumBy: empty list"
maximumBy cmp xs = foldl1 max xs
where
max x y = case cmp x y of
GT -> x
_ -> y
minimumBy :: (a -> a -> Ordering) -> [a] -> a
minimumBy cmp [] = error "List.minimumBy: empty list"
minimumBy cmp xs = foldl1 min xs
where
min x y = case cmp x y of
GT -> y
_ -> x
genericLength :: (Integral a) => [b] -> a
genericLength [] = 0
genericLength (x:xs) = 1 + genericLength xs
genericTake :: (Integral a) => a -> [b] -> [b]
genericTake _ [] = []
genericTake 0 _ = []
genericTake n (x:xs)
| n > 0 = x : genericTake (n-1) xs
| otherwise = error "List.genericTake: negative argument"
genericDrop :: (Integral a) => a -> [b] -> [b]
genericDrop 0 xs = xs
genericDrop _ [] = []
genericDrop n (_:xs)
| n > 0 = genericDrop (n-1) xs
| otherwise = error "List.genericDrop: negative argument"
genericSplitAt :: (Integral a) => a -> [b] -> ([b],[b])
genericSplitAt 0 xs = ([],xs)
genericSplitAt _ [] = ([],[])
genericSplitAt n (x:xs)
| n > 0 = (x:xs',xs'')
| otherwise = error "List.genericSplitAt: negative argument"
where (xs',xs'') = genericSplitAt (n-1) xs
genericIndex :: (Integral a) => [b] -> a -> b
genericIndex (x:_) 0 = x
genericIndex (_:xs) n
| n > 0 = genericIndex xs (n-1)
| otherwise = error "List.genericIndex: negative argument"
genericIndex _ _ = error "List.genericIndex: index too large"
genericReplicate :: (Integral a) => a -> b -> [b]
genericReplicate n x = genericTake n (repeat x)
zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
zip4 = zipWith4 (,,,)
zip5 :: [a] -> [b] -> [c] -> [d] -> [e] -> [(a,b,c,d,e)]
zip5 = zipWith5 (,,,,)
zip6 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
[(a,b,c,d,e,f)]
zip6 = zipWith6 (,,,,,)
zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] ->
[g] -> [(a,b,c,d,e,f,g)]
zip7 = zipWith7 (,,,,,,)
zipWith4 :: (a->b->c->d->e) -> [a]->[b]->[c]->[d]->[e]
zipWith4 z (a:as) (b:bs) (c:cs) (d:ds)
= z a b c d : zipWith4 z as bs cs ds
zipWith4 _ _ _ _ _ = []
zipWith5 :: (a->b->c->d->e->f) ->
[a]->[b]->[c]->[d]->[e]->[f]
zipWith5 z (a:as) (b:bs) (c:cs) (d:ds) (e:es)
= z a b c d e : zipWith5 z as bs cs ds es
zipWith5 _ _ _ _ _ _ = []
zipWith6 :: (a->b->c->d->e->f->g) ->
[a]->[b]->[c]->[d]->[e]->[f]->[g]
zipWith6 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs)
= z a b c d e f : zipWith6 z as bs cs ds es fs
zipWith6 _ _ _ _ _ _ _ = []
zipWith7 :: (a->b->c->d->e->f->g->h) ->
[a]->[b]->[c]->[d]->[e]->[f]->[g]->[h]
zipWith7 z (a:as) (b:bs) (c:cs) (d:ds) (e:es) (f:fs) (g:gs)
= z a b c d e f g : zipWith7 z as bs cs ds es fs gs
zipWith7 _ _ _ _ _ _ _ _ = []
unzip4 :: [(a,b,c,d)] -> ([a],[b],[c],[d])
unzip4 = foldr (\(a,b,c,d) ~(as,bs,cs,ds) ->
(a:as,b:bs,c:cs,d:ds))
([],[],[],[])
unzip5 :: [(a,b,c,d,e)] -> ([a],[b],[c],[d],[e])
unzip5 = foldr (\(a,b,c,d,e) ~(as,bs,cs,ds,es) ->
(a:as,b:bs,c:cs,d:ds,e:es))
([],[],[],[],[])
unzip6 :: [(a,b,c,d,e,f)] -> ([a],[b],[c],[d],[e],[f])
unzip6 = foldr (\(a,b,c,d,e,f) ~(as,bs,cs,ds,es,fs) ->
(a:as,b:bs,c:cs,d:ds,e:es,f:fs))
([],[],[],[],[],[])
unzip7 :: [(a,b,c,d,e,f,g)] -> ([a],[b],[c],[d],[e],[f],[g])
unzip7 = foldr (\(a,b,c,d,e,f,g) ~(as,bs,cs,ds,es,fs,gs) ->
(a:as,b:bs,c:cs,d:ds,e:es,f:fs,g:gs))
([],[],[],[],[],[],[])
The Haskell 98 Report
top | back | next | contents | function index
December 2002