Generic operations over list-like structures

Written by John Goerzen, jgoerzen@complete.org

Please start with the introduction at Data.ListLike#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 I/O features of ListLike may a 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.

A map in monad space. Same as sequence . map

See also rigidMapM

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.

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.

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 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.

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.