lib/prelude/list.rb in prelude-0.0.2 vs lib/prelude/list.rb in prelude-0.0.3
- old
+ new
@@ -21,536 +21,568 @@
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
#++
module Prelude
- # $Id: list.rb 7 2006-09-06 17:03:26Z prelude $
+ # $Id: list.rb 17 2006-09-17 18:03:15Z prelude $
#
# 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]
+ module List
- class List < Array
+ # head -- :: [a] -> a
+ def head(list)
+ case list
+ when [] : empty_list_error
+ else lambda { list[0] }
+ end
+ end
- # Array compatibility functions
+ # tail -- :: [a] -> [a]
+ def tail(list)
+ case list
+ when [] : empty_list_error
+ else lambda { list[1..-1] }
+ end
+ end
- alias array_plus +
+ # last -- :: [a] -> a
+ def last(list)
+ case list
+ when [] : empty_list_error
+ when [list[0]] : lambda { list[0] }
+ else last(~tail(list))
+ end
+ end
- def +(o)
- List.new(self.array_plus(o))
+ # init -- :: [a] -> [a]
+ def init(list)
+ case list
+ when [] : empty_list_error
+ when [list[0]] : lambda { [] }
+ else lambda { [~head(list)]+~init(~tail(list)) }
+ end
end
- # head -- :: [a] -> a
- def head
- self[0]
+ # null -- :: [a] -> Bool
+ def null(list)
+ lambda { list.size == 0 }
end
-
- # tail -- :: [a] -> [a]
- def tail
- self[1..-1]
+
+ # length -- :: [a] -> Int
+ def length(list)
+ lambda { list.length }
end
- # init -- :: [a] -> [a]
- def init
- self[0..-2]
+ # map -- :: (a -> b) -> [a] -> [b]
+ def map(f, list)
+ case list
+ when [] : lambda{ [] }
+ else lambda{ [ f[~head(list)] ] + ~map(f, ~tail(list)) }
+ end
end
- # null -- :: [a] -> Bool
- def null
- size == 0
+ # , reverse -- :: [a] -> [a]
+ def reverse(list)
+ r = proc { |l, a|
+ case l
+ when [] : lambda { a }
+ else lambda { ~r[~tail(l), [~head(l)]+a] }
+ end
+ }
+ r[list, []]
end
# intersperse -- :: a -> [a] -> [a]
- def intersperse
+ def intersperse(list)
warn "Method 'intersperse' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
- # -- * Reducing lists (folds)
-
- # 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. Use #foldl.
- def f_foldl(s, &block)
- empty? ? s : tail.f_foldl(block.call(s, head), &block)
+ # transpose -- :: [[a]] -> [[a]]
+ def transpose(list)
+ # FIXIT
+ lambda { list.transpose }
end
- # This is a more pedestrian iterative version of f_foldl
+ # # -- * Reducing lists (folds)
+
# foldl -- :: (a -> b -> a) -> a -> [b] -> a
- def foldl(s, &block)
- inject(s){ |a,b| block.call(a,b) }
+ def foldl(f, a, list)
+ case list
+ when [] : lambda { a }
+ else lambda { f[~foldl(f, a, ~tail(list)), ~head(list)] }
+ end
end
# foldl' -- :: (a -> b -> a) -> a -> [b] -> a
- def foldl_
+ def foldl_(list)
warn "Method 'foldl_' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
-
+
# foldl1 -- :: (a -> a -> a) -> [a] -> a
- def foldl1(&block)
- tail.foldl(head, &block)
+ def foldl1(f, list)
+ foldl(f, ~head(list), ~tail(list))
end
# foldl1' -- :: (a -> a -> a) -> [a] -> a
- def foldl1_
+ def foldl1_(list)
warn "Method 'foldl1_' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# foldr -- :: (a -> b -> b) -> b -> [a] -> b
- def foldr(s, &block)
- inject(s){ |a,b| block.call(b, a) }
+ def foldr(f, s, list)
+ case list
+ when [] : lambda { s }
+ else lambda { f[~head(list), ~foldr(f, s, ~tail(list))] }
+ end
end
# foldr1 -- :: (a -> a -> a) -> [a] -> a
- def foldr1(&block)
- tail.foldr(head, &block)
+ def foldr1(f, list)
+ foldr(f, ~head(list), ~tail(list))
end
# -- ** Special folds
- # Implemented by Array but semantics is different
# concat -- :: [[a]] -> [a]
- def concat
- flatten
+ def concat(list)
+ foldr(-:+, [], list)
end
# concatMap -- :: (a -> [b]) -> [a] -> [b]
- def concat_map
+ def concat_map(list)
warn "Method 'concatMap' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
alias concatMap concat_map
# and -- :: [Bool] -> Bool
- def and
- foldr(true){|x,y| x && y}
+ def and_(list)
+ foldr(lambda {|x,y| x && y}, true, list)
end
# or -- :: [Bool] -> Bool
- def or
- foldr(false){|x,y| (x || y)}
+ def or_(list)
+ foldr(lambda {|x,y| (x || y)}, false, list)
end
# any -- :: (a -> Bool) -> [a] -> Bool
- def any(&block)
- each{|e| return true if block.call(e)}
- return false
+ def any(f, list)
+ or_(~map(f, list))
end
# all -- :: (a -> Bool) -> [a] -> Bool
- def all(&block)
- each{|e| return false unless block.call(e)}
- return true
+ def all(f, list)
+ and_(~map(f, list))
end
# sum -- :: (Num a) => [a] -> a
- def sum
+ def sum(list)
warn "Method 'sum' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# product -- :: (Num a) => [a] -> a
- def product
+ def product(list)
warn "Method 'product' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# maximum -- :: (Ord a) => [a] -> a
- def maximum
+ def maximum(list)
warn "Method 'maximum' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# minimum -- :: (Ord a) => [a] -> a
- def minimum
+ def minimum(list)
warn "Method 'minimum' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
-
# -- * Building lists
# -- ** Scans
# scanl -- :: (a -> b -> a) -> a -> [b] -> [a]
- def scanl(s, &block)
- inject([s]){ |a,b| a << block.call(a.last,b) }
+ def scanl(f, s, list)
+ warn "Method 'scanl' is not implemented yet." if $VERBOSE
+ return lambda { [] }
end
# scanl1 -- :: (a -> a -> a) -> [a] -> [a]
- def scanl1(&block)
- tail.scanl(head, &block)
+ def scanl1(f, list)
+ warn "Method 'scanl1' is not implemented yet." if $VERBOSE
+ return lambda { [] }
end
# scanr -- :: (a -> b -> b) -> b -> [a] -> [b]
- def scanr(s, &block)
- inject([s]){ |a,b| a << block.call(b, a.last) }
+ def scanr(f, s, list)
+ warn "Method 'scanr' is not implemented yet." if $VERBOSE
+ return lambda { [] }
end
# scanr1 -- :: (a -> a -> a) -> [a] -> [a]
- def scanr1(&block)
- tail.scanr(head, &block)
+ def scanr1(f, list)
+ warn "Method 'scanr1' is not implemented yet." if $VERBOSE
+ return lambda { [] }
end
-
# -- ** Accumulating maps
# mapAccumL -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
- def map_accum_l
+ def map_accum_l(list)
warn "Method 'map_accum_l' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias mapAccumL map_accum_l
# mapAccumR -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
- def map_accum_r
+ def map_accum_r(list)
warn "Method 'map_accum_r' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias mapAccumR map_accum_r
-
# -- ** Infinite lists
# iterate -- :: (a -> a) -> a -> [a]
- def iterate
+ def iterate(list)
warn "Method 'iterate' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# repeat -- :: a -> [a]
- def repeat
+ def repeat(list)
warn "Method 'repeat' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# replicate -- :: Int -> a -> [a]
- def replicate
+ def replicate(list)
warn "Method 'replicate' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# cycle -- :: [a] -> [a]
- def cycle
+ def cycle(list)
warn "Method 'cycle' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
-
# -- ** Unfolding
# unfoldr -- :: (b -> Maybe (a, b)) -> b -> [a]
- def unfoldr
+ def unfoldr(list)
warn "Method 'unfoldr' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
-
# -- * Sublists
# -- ** Extracting sublists
# take -- :: Int -> [a] -> [a]
- def take(n)
- self[0..(n-1)]
+ def take(n, list)
+ lambda { list[0..(n-1)] }
end
# drop -- :: Int -> [a] -> [a]
- def drop(n)
- self[n..-1]
+ def drop(n, list)
+ lambda { list[n..-1] }
end
# splitAt -- :: Int -> [a] -> ([a], [a])
- def split_at(n)
- [take(n), drop(n)]
+ def split_at(n, list)
+ lambda { [~take(n, list), ~drop(n, list)] }
end
- alias splitAt split_at
# takeWhile -- :: (a -> Bool) -> [a] -> [a]
- def take_while
- r = []
- each{ |e|
- break unless yield(e)
- r << e
- }
- r
+ def take_while(p, list)
+ case list
+ when [] : lambda { [] }
+ else p[~head(list)] ? lambda { [~head(list)]+ ~take_while(p, ~tail(list)) } : lambda { [] }
+ end
end
+
alias takeWhile take_while
# dropWhile -- :: (a -> Bool) -> [a] -> [a]
- def drop_while
- r = []
- each{ |e|
- next if yield(e)
- r << e
- }
- r
+ def drop_while(p, list)
+ case list
+ when [] : lambda { [] }
+ else p[~head(list)] ? lambda { ~drop_while(p, ~tail(list)) } : lambda { list }
+ end
end
+
alias dropWhile drop_while
# span -- :: (a -> Bool) -> [a] -> ([a], [a])
- def span(&block)
- [take_while(&block), drop_while(&block)]
+ def span(p, list)
+ lambda { [~takeWhile(p, list), ~dropWhile(p,list)] }
end
# break -- :: (a -> Bool) -> [a] -> ([a], [a])
- def break
+ def break_(list)
warn "Method 'break' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# group -- :: Eq a => [a] -> [[a]]
- def group
+ def group(list)
warn "Method 'group' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# inits -- :: [a] -> [[a]]
- def inits
+ def inits(list)
warn "Method 'inits' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# tails -- :: [a] -> [[a]]
- def tails
+ def tails(list)
warn "Method 'tails' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# -- ** Predicates
# isPrefixOf -- :: (Eq a) => [a] -> [a] -> Bool
- def is_prefix_of
+ def is_prefix_of(list)
warn "Method 'is_prefix_of' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias isPrefixOf is_prefix_of
# isSuffixOf -- :: (Eq a) => [a] -> [a] -> Bool
- def is_suffix_of
+ def is_suffix_of(list)
warn "Method 'is_suffix_of' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias isSuffixOf is_suffix_of
# -- * Searching lists
# -- ** Searching by equality
# elem -- :: a -> [a] -> Bool
- def elem
+ def elem(list)
warn "Method 'elem' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# notElem -- :: a -> [a] -> Bool
- def not_elem
+ def not_elem(list)
warn "Method 'not_elem' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias notElem not_elem
-
+
# lookup -- :: (Eq a) => a -> [(a,b)] -> Maybe b
- def lookup
+ def lookup(list)
warn "Method 'lookup' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# -- ** Searching with a predicate
+ # find -- :: (a -> Bool) -> [a] -> Maybe a
+ def find(p, list)
+ warn "Method 'find' is not implemented yet." if $VERBOSE
+ return lambda { [] }
+ end
+
# filter -- :: (a -> Bool) -> [a] -> [a]
- def filter
+ def filter(list)
warn "Method 'filter' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+ # partition -- :: (a -> Bool) -> [a] -> ([a], [a])
+ def partition(p, list)
+ warn "Method 'partition' is not implemented yet." if $VERBOSE
+ return lambda { [] }
+ end
# -- * Indexing lists
# -- | These functions treat a list @xs@ as a indexed collection,
# -- with indices ranging from 0 to @'length' xs - 1@.
# elemIndex -- :: (Eq a) => a -> [a] -> Maybe Int
- def elem_index
+ def elem_index(list)
warn "Method 'elem_index' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias elemIndex elem_index
# elemIndices -- :: (Eq a) => a -> [a] -> [Int]
- def elem_indices
+ def elem_indices(list)
warn "Method 'elem_indices' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias elemIndices elem_indices
# findIndex -- :: (a -> Bool) -> [a] -> Maybe Int
- def find_index
+ def find_index(list)
warn "Method 'find_index' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias findIndex find_index
# findIndices -- :: (a -> Bool) -> [a] -> [Int]
- def find_indices
+ def find_indices(list)
warn "Method 'find_indices' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias findIndices find_indices
-
# -- * Zipping and unzipping lists
+ # zip -- :: [a] -> [b] -> [(a,b)]
+ def zip(list1, list2)
+ warn "Method 'zip' is not implemented yet." if $VERBOSE
+ return lambda { [] }
+ end
+
# zip3
- def zip3
+ def zip3(list)
warn "Method 'zip3' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# zip4, zip5, zip6, zip7
- def zip4
+ def zip4(list)
warn "Method 'zip4' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
-
# zipWith -- :: (a -> b -> c) -> [a] -> [b] -> [c]
- def zip_with
+ def zip_with(list)
warn "Method 'zip_with' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias zipWith zip_with
# zipWith3
- def zip_with3
+ def zip_with3(list)
warn "Method 'zip_with3' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias zipWith3 zip_with3
# zipWith4, zipWith5, zipWith6, zipWith7
- def zip_with4
+ def zip_with4(list)
warn "Method 'zip_with4' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
+
alias zipWith4 zip_with4
-
# unzip -- :: [(a,b)] -> ([a],[b])
- def unzip
+ def unzip(list)
warn "Method 'unzip' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# unzip3
- def unzip3
+ def unzip3(list)
warn "Method 'unzip3' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# unzip4, unzip5, unzip6, unzip7
- def unzip4
+ def unzip4(list)
warn "Method 'unzip4' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
-
# -- * Special lists
# -- ** Functions on strings
# lines -- :: String -> [String]
- def lines
+ def lines(list)
warn "Method 'lines' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# words -- :: String -> [String]
- def words
+ def words(list)
warn "Method 'words' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# unlines -- :: [String] -> String
- def unlines
+ def unlines(list)
warn "Method 'unlines' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# unwords -- :: [String] -> String
- def unwords
+ def unwords(list)
warn "Method 'unwords' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
-
# -- ** \"Set\" operations
# nub -- :: (Eq a) => [a] -> [a]
- def nub
+ def nub(list)
warn "Method 'nub' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# delete -- :: (Eq a) => a -> [a] -> [a]
- # Implemented by Array but semantics is different
- def delete(o)
+ def delete(o, list)
warn "Method 'delete' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# union -- :: (Eq a) => [a] -> [a] -> [a]
- def union
+ def union(list)
warn "Method 'union' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# intersect -- :: (Eq a) => [a] -> [a] -> [a]
- def intersect
+ def intersect(list)
warn "Method 'intersect' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
# -- ** Ordered lists
- # Implemented by Array but semantics is different
+ # sort -- :: (Ord a) => [a] -> [a]
+ def sort(list)
+ warn "Method 'sort' is not implemented yet." if $VERBOSE
+ return lambda { [] }
+ end
+
# insert -- :: (Ord a) => a -> [a] -> [a]
- def insert(o)
+ def insert(o, list)
warn "Method 'insert' is not implemented yet." if $VERBOSE
- return []
+ return lambda { [] }
end
-
-
- # def functional_fold(st, &op)
- # f = proc { |s, a|
- # if a.empty? then
- # proc { s }
- # else
- # f.call(op.call(s, a[0]), a.slice(1, a.length-1))
- # end
- # }
- # f.call(st, self)
- # end
end # List
end # Prelude