#-- 
#     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 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 program 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.
#
#     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.
#++

module Prelude

  # $Id: list.rb 2 2006-08-25 00:11:17Z 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.
  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
    
    #    , last	       -- :: [a] -> a
    # already defined by the Array
    
    #    , 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

    #    , 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]
    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
    def f_foldl(s, &block)
      empty? ? s : tail.f_foldl(block.call(s, head), &block)
    end

    # This is a more pedestrian iterative version.
    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

    #    , concat            -- :: [[a]] -> [a]
    # Implemented by Array but semantics is different
    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
    #    , find	       -- :: (a -> Bool) -> [a] -> Maybe a
    # Implemented by Array

    #    , 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
    #    -- | 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
    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

    #    , zip               -- :: [a] -> [b] -> [(a,b)]
    # Implemented by Array

    #    , 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
    

    #    , (\\)              -- :: (Eq a) => [a] -> [a] -> [a]
    # Don't know how to implement it in Ruby

    
    #    , 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
    #    , sort              -- :: (Ord a) => [a] -> [a]
    # Implemented by Array

    #    , insert            -- :: (Ord a) => a -> [a] -> [a]
    # Implemented by Array but semantics is different
    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