lib/prelude/list.rb in prelude-0.0.1 vs lib/prelude/list.rb in prelude-0.0.2
- old
+ new
@@ -4,553 +4,537 @@
#
# http://prelude.rubyforge.org
#
# Copyright (C) 2006 APP Design, Inc.
#
-# This program is free software; you can redistribute it and/or modify
-# it under the terms of the GNU General Public License as published by
-# the Free Software Foundation; either version 2 of the License, or
-# (at your option) any later version.
+# This library is free software; you can redistribute it and/or
+# modify it under the terms of the GNU Lesser General Public
+# License as published by the Free Software Foundation; either
+# version 2.1 of the License, or (at your option) any later version.
#
-# This program is distributed in the hope that it will be useful,
+# This library is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
-# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-# GNU General Public License for more details.
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+# Lesser General Public License for more details.
#
-# You should have received a copy of the GNU General Public License along
-# with this program; if not, write to the Free Software Foundation, Inc.,
-# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+# You should have received a copy of the GNU Lesser General Public
+# License along with this library; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
#++
module Prelude
- # $Id: list.rb 2 2006-08-25 00:11:17Z prelude $
+ # $Id: list.rb 7 2006-09-06 17:03:26Z prelude $
#
- # This code is inspired in part by Hipster, <hipster xs4all.nl> (a.k.a. Michel
- # van de Ven), and his original sketch was initially located at
- # http://www.xs4all.nl/~hipster/lib/ruby/haskell
- #
# This eventually needs to be implemented with lazy lists, see
# http://lazylist.rubyforge.org for details
#
# I used the signatures of Haskell's List.hs file in order not to forget to implement
# the functions defined there and to remind of what was intended.
+ #
+ # The following methods are implemented by Array with the same semantics:
+ # * last -- :: [a] -> a
+ # * length -- :: [a] -> Int
+ # * map -- :: (a -> b) -> [a] -> [b]
+ # * reverse -- :: [a] -> [a]
+ # * transpose -- :: [[a]] -> [[a]]
+ # * find -- :: (a -> Bool) -> [a] -> Maybe a
+ # * partition -- :: (a -> Bool) -> [a] -> ([a], [a])
+ # * zip -- :: [a] -> [b] -> [(a,b)]
+ # * sort -- :: (Ord a) => [a] -> [a]
+ #
+ # I do not know how to implement these in Ruby:
+ # * (!!) -- :: [a] -> Int -> a
+ # * (\\) -- :: (Eq a) => [a] -> [a] -> [a]
+
class List < Array
# Array compatibility functions
+
alias array_plus +
def +(o)
List.new(self.array_plus(o))
end
- # , head -- :: [a] -> a
+ # head -- :: [a] -> a
def head
self[0]
end
- # , last -- :: [a] -> a
- # already defined by the Array
-
- # , tail -- :: [a] -> [a]
+ # tail -- :: [a] -> [a]
def tail
self[1..-1]
end
- # , init -- :: [a] -> [a]
+ # init -- :: [a] -> [a]
def init
self[0..-2]
end
- # , null -- :: [a] -> Bool
+ # null -- :: [a] -> Bool
def null
size == 0
end
- # , length -- :: [a] -> Int
- # Implemented by Array
-
- # -- * List transformations
- # , map -- :: (a -> b) -> [a] -> [b]
- # Implemented by Array
-
- # , reverse -- :: [a] -> [a]
- # Implemented by Array
-
- # , intersperse -- :: a -> [a] -> [a]
+ # intersperse -- :: a -> [a] -> [a]
def intersperse
warn "Method 'intersperse' is not implemented yet." if $VERBOSE
return []
end
- # , transpose -- :: [[a]] -> [[a]]
- # Implemented by Array
-
# -- * Reducing lists (folds)
- # , foldl -- :: (a -> b -> a) -> a -> [b] -> a
-
# Classic recursive functional definition causes stack overflow for
# arrays of any usable size... So don't use it, it's here for
- # demonstration purposes only
+ # demonstration purposes only. Use #foldl.
def f_foldl(s, &block)
empty? ? s : tail.f_foldl(block.call(s, head), &block)
end
- # This is a more pedestrian iterative version.
+ # This is a more pedestrian iterative version of f_foldl
+ # foldl -- :: (a -> b -> a) -> a -> [b] -> a
def foldl(s, &block)
inject(s){ |a,b| block.call(a,b) }
end
- # , foldl' -- :: (a -> b -> a) -> a -> [b] -> a
+ # foldl' -- :: (a -> b -> a) -> a -> [b] -> a
def foldl_
warn "Method 'foldl_' is not implemented yet." if $VERBOSE
return []
end
- # , foldl1 -- :: (a -> a -> a) -> [a] -> a
+ # foldl1 -- :: (a -> a -> a) -> [a] -> a
def foldl1(&block)
tail.foldl(head, &block)
end
- # , foldl1' -- :: (a -> a -> a) -> [a] -> a
+ # foldl1' -- :: (a -> a -> a) -> [a] -> a
def foldl1_
warn "Method 'foldl1_' is not implemented yet." if $VERBOSE
return []
end
- # , foldr -- :: (a -> b -> b) -> b -> [a] -> b
+ # foldr -- :: (a -> b -> b) -> b -> [a] -> b
def foldr(s, &block)
inject(s){ |a,b| block.call(b, a) }
end
- # , foldr1 -- :: (a -> a -> a) -> [a] -> a
+ # foldr1 -- :: (a -> a -> a) -> [a] -> a
def foldr1(&block)
tail.foldr(head, &block)
end
# -- ** Special folds
- # , concat -- :: [[a]] -> [a]
# Implemented by Array but semantics is different
+ # concat -- :: [[a]] -> [a]
def concat
flatten
end
-
- # , concatMap -- :: (a -> [b]) -> [a] -> [b]
+ # concatMap -- :: (a -> [b]) -> [a] -> [b]
def concat_map
warn "Method 'concatMap' is not implemented yet." if $VERBOSE
return []
end
alias concatMap concat_map
- # , and -- :: [Bool] -> Bool
+ # and -- :: [Bool] -> Bool
def and
foldr(true){|x,y| x && y}
end
- # , or -- :: [Bool] -> Bool
+ # or -- :: [Bool] -> Bool
def or
foldr(false){|x,y| (x || y)}
end
- # , any -- :: (a -> Bool) -> [a] -> Bool
+ # any -- :: (a -> Bool) -> [a] -> Bool
def any(&block)
each{|e| return true if block.call(e)}
return false
end
- # , all -- :: (a -> Bool) -> [a] -> Bool
+ # all -- :: (a -> Bool) -> [a] -> Bool
def all(&block)
each{|e| return false unless block.call(e)}
return true
end
- # , sum -- :: (Num a) => [a] -> a
+ # sum -- :: (Num a) => [a] -> a
def sum
warn "Method 'sum' is not implemented yet." if $VERBOSE
return []
end
- # , product -- :: (Num a) => [a] -> a
+ # product -- :: (Num a) => [a] -> a
def product
warn "Method 'product' is not implemented yet." if $VERBOSE
return []
end
- # , maximum -- :: (Ord a) => [a] -> a
+ # maximum -- :: (Ord a) => [a] -> a
def maximum
warn "Method 'maximum' is not implemented yet." if $VERBOSE
return []
end
- # , minimum -- :: (Ord a) => [a] -> a
+ # minimum -- :: (Ord a) => [a] -> a
def minimum
warn "Method 'minimum' is not implemented yet." if $VERBOSE
return []
end
- # -- * Building lists
+ # -- * Building lists
- # -- ** Scans
- # , scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
+ # -- ** Scans
+
+ # scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
def scanl(s, &block)
inject([s]){ |a,b| a << block.call(a.last,b) }
end
- # , scanl1 -- :: (a -> a -> a) -> [a] -> [a]
+ # scanl1 -- :: (a -> a -> a) -> [a] -> [a]
def scanl1(&block)
tail.scanl(head, &block)
end
- # , scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
+ # scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
def scanr(s, &block)
inject([s]){ |a,b| a << block.call(b, a.last) }
end
- # , scanr1 -- :: (a -> a -> a) -> [a] -> [a]
+ # scanr1 -- :: (a -> a -> a) -> [a] -> [a]
def scanr1(&block)
tail.scanr(head, &block)
end
# -- ** Accumulating maps
- # , mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
+
+ # mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
def map_accum_l
warn "Method 'map_accum_l' is not implemented yet." if $VERBOSE
return []
end
alias mapAccumL map_accum_l
- # , mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
+ # mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
def map_accum_r
warn "Method 'map_accum_r' is not implemented yet." if $VERBOSE
return []
end
alias mapAccumR map_accum_r
# -- ** Infinite lists
- # , iterate -- :: (a -> a) -> a -> [a]
+
+ # iterate -- :: (a -> a) -> a -> [a]
def iterate
warn "Method 'iterate' is not implemented yet." if $VERBOSE
return []
end
- # , repeat -- :: a -> [a]
+ # repeat -- :: a -> [a]
def repeat
warn "Method 'repeat' is not implemented yet." if $VERBOSE
return []
end
- # , replicate -- :: Int -> a -> [a]
+ # replicate -- :: Int -> a -> [a]
def replicate
warn "Method 'replicate' is not implemented yet." if $VERBOSE
return []
end
- # , cycle -- :: [a] -> [a]
+ # cycle -- :: [a] -> [a]
def cycle
warn "Method 'cycle' is not implemented yet." if $VERBOSE
return []
end
# -- ** Unfolding
- # , unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
+
+ # unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
def unfoldr
warn "Method 'unfoldr' is not implemented yet." if $VERBOSE
return []
end
- # -- * Sublists
+ # -- * Sublists
- # -- ** Extracting sublists
- # , take -- :: Int -> [a] -> [a]
+ # -- ** Extracting sublists
+
+ # take -- :: Int -> [a] -> [a]
def take(n)
self[0..(n-1)]
end
- # , drop -- :: Int -> [a] -> [a]
+ # drop -- :: Int -> [a] -> [a]
def drop(n)
self[n..-1]
end
- # , splitAt -- :: Int -> [a] -> ([a], [a])
+ # splitAt -- :: Int -> [a] -> ([a], [a])
def split_at(n)
[take(n), drop(n)]
end
alias splitAt split_at
- # , takeWhile -- :: (a -> Bool) -> [a] -> [a]
+ # takeWhile -- :: (a -> Bool) -> [a] -> [a]
def take_while
r = []
each{ |e|
break unless yield(e)
r << e
}
r
end
alias takeWhile take_while
- # , dropWhile -- :: (a -> Bool) -> [a] -> [a]
+ # dropWhile -- :: (a -> Bool) -> [a] -> [a]
def drop_while
r = []
each{ |e|
next if yield(e)
r << e
}
r
end
alias dropWhile drop_while
- # , span -- :: (a -> Bool) -> [a] -> ([a], [a])
+ # span -- :: (a -> Bool) -> [a] -> ([a], [a])
def span(&block)
[take_while(&block), drop_while(&block)]
end
- # , break -- :: (a -> Bool) -> [a] -> ([a], [a])
+ # break -- :: (a -> Bool) -> [a] -> ([a], [a])
def break
warn "Method 'break' is not implemented yet." if $VERBOSE
return []
end
- # , group -- :: Eq a => [a] -> [[a]]
+ # group -- :: Eq a => [a] -> [[a]]
def group
warn "Method 'group' is not implemented yet." if $VERBOSE
return []
end
- # , inits -- :: [a] -> [[a]]
+ # inits -- :: [a] -> [[a]]
def inits
warn "Method 'inits' is not implemented yet." if $VERBOSE
return []
end
- # , tails -- :: [a] -> [[a]]
+ # tails -- :: [a] -> [[a]]
def tails
warn "Method 'tails' is not implemented yet." if $VERBOSE
return []
end
# -- ** Predicates
- # , isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
+
+ # isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
def is_prefix_of
warn "Method 'is_prefix_of' is not implemented yet." if $VERBOSE
return []
end
alias isPrefixOf is_prefix_of
- # , isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
+ # isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
def is_suffix_of
warn "Method 'is_suffix_of' is not implemented yet." if $VERBOSE
return []
end
alias isSuffixOf is_suffix_of
- # -- * Searching lists
+ # -- * Searching lists
# -- ** Searching by equality
- # , elem -- :: a -> [a] -> Bool
+
+ # elem -- :: a -> [a] -> Bool
def elem
warn "Method 'elem' is not implemented yet." if $VERBOSE
return []
end
- # , notElem -- :: a -> [a] -> Bool
+ # notElem -- :: a -> [a] -> Bool
def not_elem
warn "Method 'not_elem' is not implemented yet." if $VERBOSE
return []
end
alias notElem not_elem
- # , lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
+ # lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
def lookup
warn "Method 'lookup' is not implemented yet." if $VERBOSE
return []
end
# -- ** Searching with a predicate
- # , find -- :: (a -> Bool) -> [a] -> Maybe a
- # Implemented by Array
- # , filter -- :: (a -> Bool) -> [a] -> [a]
+ # filter -- :: (a -> Bool) -> [a] -> [a]
def filter
warn "Method 'filter' is not implemented yet." if $VERBOSE
return []
end
- # , partition -- :: (a -> Bool) -> [a] -> ([a], [a])
- # Implemented by Array
+ # -- * Indexing lists
- # -- * Indexing lists
# -- | These functions treat a list @xs@ as a indexed collection,
# -- with indices ranging from 0 to @'length' xs - 1@.
- # , (!!) -- :: [a] -> Int -> a
- # Don't know how to implement it in Ruby
-
- # , elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
+ # elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
def elem_index
warn "Method 'elem_index' is not implemented yet." if $VERBOSE
return []
end
alias elemIndex elem_index
- # , elemIndices -- :: (Eq a) => a -> [a] -> [Int]
+ # elemIndices -- :: (Eq a) => a -> [a] -> [Int]
def elem_indices
warn "Method 'elem_indices' is not implemented yet." if $VERBOSE
return []
end
alias elemIndices elem_indices
- # , findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
+ # findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
def find_index
warn "Method 'find_index' is not implemented yet." if $VERBOSE
return []
end
alias findIndex find_index
- # , findIndices -- :: (a -> Bool) -> [a] -> [Int]
+ # findIndices -- :: (a -> Bool) -> [a] -> [Int]
def find_indices
warn "Method 'find_indices' is not implemented yet." if $VERBOSE
return []
end
alias findIndices find_indices
- # -- * Zipping and unzipping lists
+ # -- * Zipping and unzipping lists
- # , zip -- :: [a] -> [b] -> [(a,b)]
- # Implemented by Array
-
- # , zip3
+ # zip3
def zip3
warn "Method 'zip3' is not implemented yet." if $VERBOSE
return []
end
- # , zip4, zip5, zip6, zip7
+ # zip4, zip5, zip6, zip7
def zip4
warn "Method 'zip4' is not implemented yet." if $VERBOSE
return []
end
- # , zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
+ # zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
def zip_with
warn "Method 'zip_with' is not implemented yet." if $VERBOSE
return []
end
alias zipWith zip_with
- # , zipWith3
+ # zipWith3
def zip_with3
warn "Method 'zip_with3' is not implemented yet." if $VERBOSE
return []
end
alias zipWith3 zip_with3
- # , zipWith4, zipWith5, zipWith6, zipWith7
+ # zipWith4, zipWith5, zipWith6, zipWith7
def zip_with4
warn "Method 'zip_with4' is not implemented yet." if $VERBOSE
return []
end
alias zipWith4 zip_with4
- # , unzip -- :: [(a,b)] -> ([a],[b])
+ # unzip -- :: [(a,b)] -> ([a],[b])
def unzip
warn "Method 'unzip' is not implemented yet." if $VERBOSE
return []
end
- # , unzip3
+ # unzip3
def unzip3
warn "Method 'unzip3' is not implemented yet." if $VERBOSE
return []
end
- # , unzip4, unzip5, unzip6, unzip7
+ # unzip4, unzip5, unzip6, unzip7
def unzip4
warn "Method 'unzip4' is not implemented yet." if $VERBOSE
return []
end
- # -- * Special lists
+ # -- * Special lists
# -- ** Functions on strings
- # , lines -- :: String -> [String]
+
+ # lines -- :: String -> [String]
def lines
warn "Method 'lines' is not implemented yet." if $VERBOSE
return []
end
- # , words -- :: String -> [String]
+ # words -- :: String -> [String]
def words
warn "Method 'words' is not implemented yet." if $VERBOSE
return []
end
- # , unlines -- :: [String] -> String
+ # unlines -- :: [String] -> String
def unlines
warn "Method 'unlines' is not implemented yet." if $VERBOSE
return []
end
- # , unwords -- :: [String] -> String
+ # unwords -- :: [String] -> String
def unwords
warn "Method 'unwords' is not implemented yet." if $VERBOSE
return []
end
# -- ** \"Set\" operations
- # , nub -- :: (Eq a) => [a] -> [a]
+ # nub -- :: (Eq a) => [a] -> [a]
def nub
warn "Method 'nub' is not implemented yet." if $VERBOSE
return []
end
-
- # , delete -- :: (Eq a) => a -> [a] -> [a]
+ # delete -- :: (Eq a) => a -> [a] -> [a]
# Implemented by Array but semantics is different
def delete(o)
warn "Method 'delete' is not implemented yet." if $VERBOSE
return []
end
-
- # , (\\) -- :: (Eq a) => [a] -> [a] -> [a]
- # Don't know how to implement it in Ruby
-
-
- # , union -- :: (Eq a) => [a] -> [a] -> [a]
+ # union -- :: (Eq a) => [a] -> [a] -> [a]
def union
warn "Method 'union' is not implemented yet." if $VERBOSE
return []
end
- # , intersect -- :: (Eq a) => [a] -> [a] -> [a]
+ # intersect -- :: (Eq a) => [a] -> [a] -> [a]
def intersect
warn "Method 'intersect' is not implemented yet." if $VERBOSE
return []
end
-
# -- ** Ordered lists
- # , sort -- :: (Ord a) => [a] -> [a]
- # Implemented by Array
- # , insert -- :: (Ord a) => a -> [a] -> [a]
# Implemented by Array but semantics is different
+ # insert -- :: (Ord a) => a -> [a] -> [a]
def insert(o)
warn "Method 'insert' is not implemented yet." if $VERBOSE
return []
end