#-- 
#     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 7 2006-09-06 17:03:26Z 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]

  class List < Array

    # Array compatibility functions

    alias array_plus +

    def +(o)
      List.new(self.array_plus(o))
    end

    # head           -- :: [a] -> a
    def head
      self[0]
    end
    
    # tail           -- :: [a] -> [a]
    def tail
      self[1..-1]
    end

    # init              -- :: [a] -> [a]
    def init
      self[0..-2]
    end

    # null           -- :: [a] -> Bool
    def null
      size == 0
    end

    # intersperse       -- :: a -> [a] -> [a]
    def intersperse
      warn "Method 'intersperse' is not implemented yet." if $VERBOSE
      return []
    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)
    end

    # 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
    def foldl_
      warn "Method 'foldl_' is not implemented yet." if $VERBOSE
      return []
    end

    # foldl1	       -- :: (a -> a -> a) -> [a] -> a
    def foldl1(&block)
      tail.foldl(head, &block)
    end

    # 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
    def foldr(s, &block)
      inject(s){ |a,b| block.call(b, a) }
    end

    # foldr1            -- :: (a -> a -> a) -> [a] -> a
    def foldr1(&block)
      tail.foldr(head, &block)
    end

    #    -- ** Special folds

    # Implemented by Array but semantics is different
    # concat            -- :: [[a]] -> [a]
    def concat
      flatten
    end

    # 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
    def and
        foldr(true){|x,y| x && y}
    end

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

    # any               -- :: (a -> Bool) -> [a] -> Bool
    def any(&block)
      each{|e| return true if block.call(e)}
      return false
    end

    # all               -- :: (a -> Bool) -> [a] -> Bool
    def all(&block)
      each{|e| return false unless block.call(e)}
      return true
    end

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

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

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

    # minimum           -- :: (Ord a) => [a] -> a
    def minimum
      warn "Method 'minimum' is not implemented yet." if $VERBOSE
      return []
    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) }
    end

    # scanl1            -- :: (a -> a -> a) -> [a] -> [a]
    def scanl1(&block)
      tail.scanl(head, &block)
    end

    # 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]
    def scanr1(&block)
      tail.scanr(head, &block)
    end


    #    -- ** Accumulating maps

    # 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])
    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]
    def iterate
      warn "Method 'iterate' is not implemented yet." if $VERBOSE
      return []
    end

    # repeat            -- :: a -> [a]
    def repeat
      warn "Method 'repeat' is not implemented yet." if $VERBOSE
      return []
    end

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

    # cycle             -- :: [a] -> [a]
    def cycle
      warn "Method 'cycle' is not implemented yet." if $VERBOSE
      return []
    end


    #    -- ** Unfolding

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


    #   -- * Sublists

    #   -- ** Extracting sublists

    # take              -- :: Int -> [a] -> [a]
    def take(n)
      self[0..(n-1)]
    end

    # drop              -- :: Int -> [a] -> [a]
    def drop(n)
      self[n..-1]
    end

    # splitAt           -- :: Int -> [a] -> ([a], [a])
    def split_at(n)
      [take(n), drop(n)]
    end
    alias splitAt split_at

    # 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]
    def drop_while
      r = []
      each{ |e|
        next if yield(e)
        r << e
      }
      r
    end
    alias dropWhile drop_while

    # span              -- :: (a -> Bool) -> [a] -> ([a], [a])
    def span(&block)
      [take_while(&block), drop_while(&block)]
    end

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

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

    # inits             -- :: [a] -> [[a]]
    def inits
      warn "Method 'inits' is not implemented yet." if $VERBOSE
      return []
    end

    # tails             -- :: [a] -> [[a]]
    def tails
      warn "Method 'tails' is not implemented yet." if $VERBOSE
      return []
    end

    #    -- ** Predicates

    # 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
    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 by equality

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

    # 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
    def lookup
      warn "Method 'lookup' is not implemented yet." if $VERBOSE
      return []
    end

    #    -- ** Searching with a predicate

    # filter	       -- :: (a -> Bool) -> [a] -> [a]
    def filter
      warn "Method 'filter' is not implemented yet." if $VERBOSE
      return []
    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
      warn "Method 'elem_index' is not implemented yet." if $VERBOSE
      return []
    end
    alias elemIndex elem_index

    # 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
    def find_index
      warn "Method 'find_index' is not implemented yet." if $VERBOSE
      return []
    end
    alias findIndex find_index

    # 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

    # zip3  
    def zip3
      warn "Method 'zip3' is not implemented yet." if $VERBOSE
      return []
    end

    # zip4, zip5, zip6, zip7
    def zip4
      warn "Method 'zip4' is not implemented yet." if $VERBOSE
      return []
    end


    # 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
    def zip_with3
      warn "Method 'zip_with3' is not implemented yet." if $VERBOSE
      return []
    end
    alias zipWith3 zip_with3

    # 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])
    def unzip
      warn "Method 'unzip' is not implemented yet." if $VERBOSE
      return []
    end

    # unzip3
    def unzip3
      warn "Method 'unzip3' is not implemented yet." if $VERBOSE
      return []
    end

    # unzip4, unzip5, unzip6, unzip7
    def unzip4
      warn "Method 'unzip4' is not implemented yet." if $VERBOSE
      return []
    end


    #   -- * Special lists

    #    -- ** Functions on strings

    # lines	       -- :: String   -> [String]
    def lines
      warn "Method 'lines' is not implemented yet." if $VERBOSE
      return []
    end

    # words	       -- :: String   -> [String]
    def words
      warn "Method 'words' is not implemented yet." if $VERBOSE
      return []
    end

    # unlines           -- :: [String] -> String
    def unlines
      warn "Method 'unlines' is not implemented yet." if $VERBOSE
      return []
    end

    # unwords           -- :: [String] -> String
    def unwords
      warn "Method 'unwords' is not implemented yet." if $VERBOSE
      return []
    end


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

    # 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

    # 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]
    def intersect
      warn "Method 'intersect' is not implemented yet." if $VERBOSE
      return []
    end

    #    -- ** Ordered lists

    # 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

    
    #   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