#-- 
#     This file is part of the Prelude library that provides tools to
#     enable Haskell style functional programming in Ruby.
#
#     http://prelude.rubyforge.org 
#     
#     Copyright (C) 2006 APP Design, Inc.
#
#     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 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
#     Lesser General Public License for more details.
#
#     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 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.
  module List

    # head           -- :: [a] -> a
    def head(list)
      case list
      when [] : empty_list_error
      else      lambda { list[0] }
      end
    end

    # tail           -- :: [a] -> [a]
    def tail(list)
      case list
      when [] : empty_list_error
      else      lambda { list[1..-1] }
      end
    end

    # last           -- :: [a] -> a
    def last(list)
      case list
      when []        : empty_list_error
      when [list[0]] : lambda { list[0] }
      else             last(~tail(list))
      end
    end

    # 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

    # null           -- :: [a] -> Bool
    def null(list)
      lambda { list.size == 0 }
    end

    # length	       -- :: [a] -> Int
    def length(list)
      lambda { list.length }
    end

    # map               -- :: (a -> b) -> [a] -> [b]
    def map(f, list)
      case list
      when [] : lambda{ [] }
      else      lambda{ [ f[~head(list)] ] + ~map(f, ~tail(list)) }
      end
    end

    #    , 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(list)
      warn "Method 'intersperse' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # transpose         -- :: [[a]] -> [[a]]
    def transpose(list)
      # FIXIT
      lambda { list.transpose }
    end

    #     #    -- * Reducing lists (folds)

    # foldl           -- :: (a -> b -> a) -> a -> [b] -> a
    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_(list)
      warn "Method 'foldl_' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end
    
    # foldl1	       -- :: (a -> a -> a) -> [a] -> a
    def foldl1(f, list)
      foldl(f, ~head(list), ~tail(list))
    end

    # foldl1'	       -- :: (a -> a -> a) -> [a] -> a
    def foldl1_(list)
      warn "Method 'foldl1_' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # foldr             -- :: (a -> b -> b) -> b -> [a] -> b
    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(f, list)
      foldr(f, ~head(list), ~tail(list))
    end

    #    -- ** Special folds

    # concat            -- :: [[a]] -> [a]
    def concat(list)
      foldr(-:+, [], list)
    end

    # concatMap         -- :: (a -> [b]) -> [a] -> [b]
    def concat_map(list)
      warn "Method 'concatMap' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end
    alias concatMap concat_map

    # and	       -- :: [Bool] -> Bool
    def and_(list)
      foldr(lambda {|x,y| x && y}, true, list)
    end

    # or                -- :: [Bool] -> Bool
    def or_(list)
      foldr(lambda {|x,y| (x || y)}, false, list)
    end

    # any               -- :: (a -> Bool) -> [a] -> Bool
    def any(f, list)
      or_(~map(f, list))
    end

    # all               -- :: (a -> Bool) -> [a] -> Bool
    def all(f, list)
      and_(~map(f, list))
    end

    # sum               -- :: (Num a) => [a] -> a
    def sum(list)
      warn "Method 'sum' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # product           -- :: (Num a) => [a] -> a
    def product(list)
      warn "Method 'product' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # maximum           -- :: (Ord a) => [a] -> a
    def maximum(list)
      warn "Method 'maximum' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # minimum           -- :: (Ord a) => [a] -> a
    def minimum(list)
      warn "Method 'minimum' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    #   -- * Building lists

    #   -- ** Scans

    # scanl             -- :: (a -> b -> a) -> a -> [b] -> [a]
    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(f, list)
      warn "Method 'scanl1' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # scanr             -- :: (a -> b -> b) -> b -> [a] -> [b]
    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(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(list)
      warn "Method 'map_accum_l' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    alias mapAccumL map_accum_l

    # mapAccumR         -- :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])
    def map_accum_r(list)
      warn "Method 'map_accum_r' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    alias mapAccumR map_accum_r

    #    -- ** Infinite lists

    # iterate           -- :: (a -> a) -> a -> [a]
    def iterate(list)
      warn "Method 'iterate' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # repeat            -- :: a -> [a]
    def repeat(list)
      warn "Method 'repeat' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # replicate         -- :: Int -> a -> [a]
    def replicate(list)
      warn "Method 'replicate' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # cycle             -- :: [a] -> [a]
    def cycle(list)
      warn "Method 'cycle' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    #    -- ** Unfolding

    # unfoldr	       -- :: (b -> Maybe (a, b)) -> b -> [a]
    def unfoldr(list)
      warn "Method 'unfoldr' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    #   -- * Sublists

    #   -- ** Extracting sublists

    # take              -- :: Int -> [a] -> [a]
    def take(n, list)
      lambda { list[0..(n-1)] }
    end

    # drop              -- :: Int -> [a] -> [a]
    def drop(n, list)
      lambda { list[n..-1] }
    end

    # splitAt           -- :: Int -> [a] -> ([a], [a])
    def split_at(n, list)
      lambda { [~take(n, list), ~drop(n, list)] }
    end

    # takeWhile         -- :: (a -> Bool) -> [a] -> [a]
    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(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(p, list)
      lambda { [~takeWhile(p, list), ~dropWhile(p,list)] }
    end

    # break             -- :: (a -> Bool) -> [a] -> ([a], [a])
    def break_(list)
      warn "Method 'break' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # group             -- :: Eq a => [a] -> [[a]]
    def group(list)
      warn "Method 'group' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # inits             -- :: [a] -> [[a]]
    def inits(list)
      warn "Method 'inits' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # tails             -- :: [a] -> [[a]]
    def tails(list)
      warn "Method 'tails' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    #    -- ** Predicates

    # isPrefixOf        -- :: (Eq a) => [a] -> [a] -> Bool
    def is_prefix_of(list)
      warn "Method 'is_prefix_of' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end
    
    alias isPrefixOf is_prefix_of

    # isSuffixOf        -- :: (Eq a) => [a] -> [a] -> Bool
    def is_suffix_of(list)
      warn "Method 'is_suffix_of' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    alias isSuffixOf is_suffix_of

    #   -- * Searching lists

    #    -- ** Searching by equality

    # elem              -- :: a -> [a] -> Bool
    def elem(list)
      warn "Method 'elem' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # notElem           -- :: a -> [a] -> Bool
    def not_elem(list)
      warn "Method 'not_elem' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    alias notElem not_elem

    # lookup            -- :: (Eq a) => a -> [(a,b)] -> Maybe b
    def lookup(list)
      warn "Method 'lookup' is not implemented yet." if $VERBOSE
      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(list)
      warn "Method 'filter' is not implemented yet." if $VERBOSE
      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(list)
      warn "Method 'elem_index' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    alias elemIndex elem_index

    # elemIndices       -- :: (Eq a) => a -> [a] -> [Int]
    def elem_indices(list)
      warn "Method 'elem_indices' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    alias elemIndices elem_indices

    # findIndex	       -- :: (a -> Bool) -> [a] -> Maybe Int
    def find_index(list)
      warn "Method 'find_index' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    alias findIndex find_index

    # findIndices       -- :: (a -> Bool) -> [a] -> [Int]
    def find_indices(list)
      warn "Method 'find_indices' is not implemented yet." if $VERBOSE
      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(list)
      warn "Method 'zip3' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # zip4, zip5, zip6, zip7
    def zip4(list)
      warn "Method 'zip4' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # zipWith           -- :: (a -> b -> c) -> [a] -> [b] -> [c]
    def zip_with(list)
      warn "Method 'zip_with' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    alias zipWith zip_with

    # zipWith3
    def zip_with3(list)
      warn "Method 'zip_with3' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    alias zipWith3 zip_with3

    # zipWith4, zipWith5, zipWith6, zipWith7
    def zip_with4(list)
      warn "Method 'zip_with4' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    alias zipWith4 zip_with4

    # unzip             -- :: [(a,b)] -> ([a],[b])
    def unzip(list)
      warn "Method 'unzip' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # unzip3
    def unzip3(list)
      warn "Method 'unzip3' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # unzip4, unzip5, unzip6, unzip7
    def unzip4(list)
      warn "Method 'unzip4' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    #   -- * Special lists

    #    -- ** Functions on strings

    # lines	       -- :: String   -> [String]
    def lines(list)
      warn "Method 'lines' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # words	       -- :: String   -> [String]
    def words(list)
      warn "Method 'words' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # unlines           -- :: [String] -> String
    def unlines(list)
      warn "Method 'unlines' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # unwords           -- :: [String] -> String
    def unwords(list)
      warn "Method 'unwords' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    #    -- ** \"Set\" operations
    
    # nub               -- :: (Eq a) => [a] -> [a]
    def nub(list)
      warn "Method 'nub' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # delete            -- :: (Eq a) => a -> [a] -> [a]
    def delete(o, list)
      warn "Method 'delete' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # union             -- :: (Eq a) => [a] -> [a] -> [a]
    def union(list)
      warn "Method 'union' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    # intersect         -- :: (Eq a) => [a] -> [a] -> [a]
    def intersect(list)
      warn "Method 'intersect' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

    #    -- ** Ordered lists

    # 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, list)
      warn "Method 'insert' is not implemented yet." if $VERBOSE
      return lambda { [] }
    end

  end # List

end # Prelude