{-
Copyright (C) 2007 John Goerzen <jgoerzen@complete.org>

All rights reserved.

For license and copyright information, see the file COPYRIGHT

-}

{- |
   Module     : Data.ListLike
   Copyright  : Copyright (C) 2007 John Goerzen
   License    : LGPL

   Maintainer : John Goerzen <jgoerzen@complete.org>
   Stability  : provisional
   Portability: portable

Generic operations over list-like structures

Written by John Goerzen, jgoerzen\@complete.org

Please start with the introduction at "Data.ListLike#intro".
-}

module Data.ListLike 
                (-- * Introduction
                 -- $intro
                 
                 -- * Creation & Basic Functions
                 empty, singleton, 
                 cons, snoc, append, head, last, tail, init, null, length,
                 -- * List transformations
                 map, rigidMap, reverse, intersperse,
                 -- ** Conversions
                 toList, fromList, fromListLike,
                 -- * Reducing lists (folds), from "FoldableLL"
                 foldl, foldl', foldl1, foldr, foldr', foldr1,
                 -- ** Special folds
                 concat, concatMap, rigidConcatMap,
                 and, or,
                 any, all,
                 sum, product,
                 maximum, minimum,
                 fold, foldMap,
                 -- * Building lists
                 -- ** Scans
                 -- ** Accumulating maps
                 -- ** Infinite lists
                 iterate, repeat, replicate, cycle,
                 -- ** Unfolding
                 -- * Sublists
                 -- ** Extracting sublists
                 take, drop, splitAt, takeWhile, dropWhile, span, break,
                 group, inits, tails, 
                 -- ** Predicates
                 isPrefixOf, isSuffixOf, isInfixOf,
                 -- * Searching lists
                 -- ** Searching by equality
                 elem, notElem,
                 -- ** Searching with a predicate
                 find, filter, partition,
                 -- * Indexing lists
                 index, elemIndex, elemIndices, findIndex, findIndices,
                 -- * Zipping and unzipping lists
                 zip, zipWith, unzip,
                 -- * Monadic Operations
                 sequence, sequence_, mapM, rigidMapM, mapM_,
                 -- * Input and Output
                 ListLikeIO(..),
                 -- * Special lists
                 -- ** Strings
                 toString, fromString, lines, words,
                 -- ** \"Set\" operations
                 nub, delete, deleteFirsts, union, intersect,
                 -- ** Ordered lists
                 sort, insert,
                 -- * Generalized functions
                 -- ** The \"By\" operations
                 -- *** User-supplied equality (replacing an Eq context)
                 nubBy, deleteBy, deleteFirstsBy, unionBy, intersectBy,
                 groupBy,
                 -- *** User-supplied comparison (replacing an Ord context)
                 sortBy, insertBy, -- maximumBy, minimumBy,
                 -- ** The \"generic\" operations
                 genericLength, genericTake, genericDrop, genericSplitAt,
                 -- genericIndex,
                 genericReplicate,
                 -- * Notes on specific instances
                 -- ** Lists
                 -- $noteslist

                 -- ** Arrays
                 -- $notesarray

                 -- ** Maps
                 -- $notesmap

                 -- ** ByteStrings
                 -- $notesbytestring
                 
                 -- * Base Typeclasses
                 -- ** The ListLike class
                 ListLike,
                 -- ** The FoldableLL class
                 FoldableLL,
                 -- ** The StringLike class
                 StringLike,
                 -- ** The InfiniteListLike class
                 InfiniteListLike
                )
       where
import Prelude hiding (length, head, last, null, tail, map, filter, concat, 
                       any, lookup, init, all, foldl, foldr, foldl1, foldr1,
                       maximum, minimum, iterate, span, break, takeWhile,
                       dropWhile, reverse, zip, zipWith, sequence,
                       sequence_, mapM, mapM_, concatMap, and, or, sum,
                       product, repeat, replicate, cycle, take, drop,
                       splitAt, elem, notElem, unzip, lines, words,
                       unlines, unwords)
import Data.ListLike.Base
import Data.ListLike.FoldableLL
import Data.ListLike.Instances()
import Data.ListLike.String
import Data.ListLike.Utils
import Data.ListLike.IO

{- $intro
 #intro#
Welcome to ListLike.

This module provides abstractions over typical list operations.
It is designed to let you freely interchange different ways to represent
sequences of data.  It works with lists, various types of ByteStrings,
and much more.

In this module, you'll find generic versions of most of the functions
you're used to using in the "Prelude", "Data.List", and "System.IO".
They carry the
same names, too.  Therefore, you'll want to be careful how you import
the module.  I suggest using:

>import qualified ListLike as LL

Then, you can use LL.fold, LL.map, etc. to get the generic version of
the functions you want.  Alternatively, you can hide the other versions
from Prelude and import specific generic functions from here, such as:

>import Prelude hiding (map)
>import ListLike (map)

The module "Data.ListLike" actually simply re-exports the items found
in a number of its sub-modules.  If you want a smaller subset of
"Data.ListLike", look at the documentation for its sub-modules and import
the relevant one.

In most cases, functions here can act as drop-in replacements for their
list-specific counterparts.  They will use the same underlying implementations
for lists, so there should be no performance difference.
    
You can make your own types instances of 'ListLike' as well.  For more
details, see the notes for the 'ListLike' typeclass.
-}

{- $noteslist

Functions for operating on regular lists almost all use the native
implementations in "Data.List", "Prelude", or similar standard
modules.  The exceptions are:

* 'mapM' uses the default 'ListLike' implementation

* 'hGet' does not exist for 'String' in the Haskell modules.
  It is implemented in terms of "Data.ByteString.Lazy".

* 'hGetNonBlocking' is the same way. -}

{- $notesarray

'Data.Array.Array' is an instance of 'ListLike'.  Here are some notes about it:

* The index you use must be an integral

* 'ListLike' functions that take an index always take a 0-based index
  for compatibility with other 'ListLike' instances.
  This is translated by the instance functions into the proper offset from
  the bounds in the Array.

* 'ListLike' functions preserve the original Array index numbers when
  possible.  Functions such as 'cons' will reduce the lower bound to do
  their job.  'snoc' and 'append' increase the upper bound.  'drop' raises
  the lower bound and 'take' lowers the upper bound.

* Functions that change the length of the array by an amount not known
  in advance, such as 'filter', will generate a new array with the lower
  bound set to 0.  Furthermore, these functions cannot operate on infinite
  lists because they must know their length in order to generate the
  array.  'hGetContents' and its friends will therefore require the
  entire file to be read into memory before processing is possible.

* 'empty', 'singleton', and 'fromList' also generate an array with the
  lower bound set to 0.

* Many of these functions will generate runtime exceptions if you have
  not assigned a value to every slot in the array.
-}

{- $notesmap

'Data.Map.Map' is an instance of 'ListLike' and is a rather interesting one at
that.  The \"item\" for the Map instance is a @(key, value)@ pair.  This
permits you to do folds, maps, etc. over a Map just like you would on a list.

The nature of a Map -- that every key is unique, and that it is internally
sorted -- means that there are some special things to take note of:

* 'cons' may or may not actually increase the size of the Map.  If the given
   key is already in the map, its value will simply be updated.  Since
   a Map has a set internal ordering, it is also not guaranteed that cons
   will add something to the beginning of the Map.

* 'snoc' is the same operation as 'cons'.

* 'append' is 'Data.Map.union'

* 'nub', 'nubBy',
  'reverse', 'sort', 'sortBy', etc. are the identity function and don\'t
  actually perform any computation

* 'insert' is the same as 'cons'.

* 'replicate' and 'genericReplicate' ignore the count and return a Map
  with a single element.
-}

{- $notesbytestring

Both strict and lazy ByteStreams can be used with 'ListLike'.

Most 'ListLike' operations map directly to ByteStream options.  Notable
exceptions:

* 'map' uses the 'ListLike' implementation.  'rigidMap' is more efficient.
  The same goes for 'concatMap' vs. 'rigidConcatMap'.

* 'isInfixOf', 'sequence', 'mapM' and similar monad operations, 'insert', 
  'union', 'intersect', 'sortBy', and similar functions are not implemented
  in 'ByteStream' and use a naive default implementation.

* The lazy ByteStream module implements fewer funtions than the strict
  ByteStream module.  In some cases, default implementations are used.
  In others, notably related to I\/O, the lazy ByteStreams are converted
  back and forth to strict ones as appropriate.

-}