# List function suggestions

### From HaskellWiki

m (→groupOn and sortOn: fix type signatures for groupOn + groupOn') |
(findSublistIndex) |
||

Line 192: | Line 192: | ||

See [http://hackage.haskell.org/packages/archive/utility-ht/0.0.1/doc/html/Data-List-Key.html utility-ht] package. | See [http://hackage.haskell.org/packages/archive/utility-ht/0.0.1/doc/html/Data-List-Key.html utility-ht] package. | ||

+ | |||

+ | == Indexing lists == | ||

+ | |||

+ | * Find the index of a sublist in a list | ||

+ | <haskell> | ||

+ | findSublistIndex :: Eq a => [a] -> [a] -> Maybe Int | ||

+ | findSublistIndex xss xs = findIndex (isPrefixOf xss) $ tails xs | ||

+ | |||

+ | -- Examples | ||

+ | findSublistIndex findSublistIndex [5,6] [1..] == Just 4 | ||

+ | findSublistIndex "abbc" "abcabbc" == Just 3 | ||

+ | findSublistIndex [2,1] [2,4..10] == Nothing | ||

+ | </haskell> | ||

== See also == | == See also == |

## Latest revision as of 11:14, 16 June 2012

This page lists proposed extensions to the Haskell list functions, whether in the Prelude or Data.List. Please discuss the proposals on the Talk Page or the libraries list, and use this page to record the results of discussions. However, since the advent of HackageDB and Cabal-Install it is preferred to provide such functionality in specialised packages, rather than extending the already large base library.

## Contents |

## [edit] 1 Splitting on a separator, etc

We need these useful functions in Data.List; I'll call them 'split' (and variants) and 'replace'. These are easily implemented but everyone always reinvents them. Various versions have been proposed, but there was no consensus on which was best, e.g.

Note: a lot of good points (diverging opinions!) are covered in the mailing lists, but if we include all these various cases, split* will have 9 variants! The goal is to reach some kind of reasonable consensus, specifically on naming and semantics. Even if we need pairs of functions to satisfy various usage and algebraic needs. Failing to accommodate every possible use of these functions should not be a sufficient reason to abandon the whole project.

The goal is clarity/uniformity (everyone uses them widely and recognizes them) and portability (I don't have to keep reimplementing these or copying that one file UsefulMissingFunctions.hs).

Note: I (Jared Updike) am working with the belief that efficiency should not be a valid argument to bar these otherwise universally useful functions from the libraries; regexes are overkill for 'split' and 'replace' for common simple situations. Let's assume people will know (or learn) when they need heavier machinery (regexes, ByteString) and will use it when efficiency is important. We can try to facilitate this by reusing any names from ByteString, etc.

### [edit] 1.1 split (working name)

First of all: Check out whether the split package provides, what you need.

We need a few of these:

split :: Eq a => a -> [a] -> [[a]] splitWith :: (a -> Bool) -> [a] -> [[a]] tokens :: (a -> Bool) -> [a] -> [[a]]

That preserve:

join sep . split sep = id

See below for 'join'

And some that use above split but filter to remove empty elements (but do not preserve above property). Easy enough:

split' :: Eq a => a -> [a] -> [[a]] splitWith' :: (a -> Bool) -> [a] -> [[a]] tokens' :: (a -> Bool) -> [a] -> [[a]]

i.e.

split' sep = filter (not . null) . split sep

Usage would be:

tokensws = tokens' (`elem` " \f\v\t\n\r\b") tokensws "Hello there\n \n Haskellers! " == ["Hello", "there", "Haskellers!"]

**TODO: add version like python with multi-element separator**

**TODO: give code, copy-paste from threads mentioned above**

**TODO: list names and reasons for/against**

### [edit] 1.2 replace (working name)

replace :: [a] -> [a] -> [a] -> [a]

like Python replace:

replace "the" "a" "the quick brown fox jumped over the lazy black dog" ===> "a quick brown fox jumped over a lazy black dog"

**TODO: give code, copy-paste from threads mentioned above**

**TODO: list names and reasons for/against**

Implemented for instance in utility-ht.

### [edit] 1.3 join (working name)

join :: [a] -> [[a]] -> [a]

join sep = concat . intersperse sep

Note: this function has been implemented as 'intercalate' in Data.List.

**TODO: copy-paste things from threads mentioned above**

**TODO: list names and reasons for/against**

## [edit] 2 Sorted lists

The following are versions of standard prelude functions, but intended for sorted lists. The advantage is that they frequently reduce execution time by an O(n). The disadvantage is that the elements have to be members of Ord, and the lists have to be already sorted.

-- Eliminates duplicate entries from the list, where duplication is defined -- by the 'eq' function. The last value is kept. sortedNubBy :: (a -> a -> Bool) -> [a] -> [a] sortedNubBy eq (x1 : xs@(x2 : _)) = if eq x1 x2 then sortedNubBy eq xs else x1 : sortedNubBy eq xs sortedNubBy _ xs = xs sortedNub :: (Eq a) => [a] -> [a] sortedNub = sortedNubBy (==) -- Merge two sorted lists into a new sorted list. Where elements are equal -- the element from the first list is taken first. mergeBy :: (a -> a -> Ordering) -> [a] -> [a] -> [a] mergeBy cmp xs@(x1:xs1) ys@(y1:ys1) = if cmp x1 y1 == GT then y1 : mergeBy cmp xs ys1 else x1 : mergeBy cmp xs1 ys mergeBy _ [] ys = ys mergeBy _ xs [] = xs merge :: (Ord a) => [a] -> [a] -> [a] merge = mergeBy compare

## [edit] 3 Generalize groupBy and friends

In the Haskell 98 List library,groupBy :: (a -> a -> Bool) -> [a] -> [[a]] groupBy rel [] = [] groupBy rel (x:xs) = (x:ys) : groupBy rel zs where (ys,zs) = groupByAux x xs groupByAux x0 (x:xs) | rel x0 x = (x:ys, zs) where (ys,zs) = groupByAux x xs groupByAux y xs = ([], xs)

However it is also useful on other relations, e.g.

- Picking out maximal ascending sublists (runs):

> groupBy (<=) [7,3,5,9,6,8,3,5,4] [[7],[3,5,9],[6,8],[3,5],[4]]

- Picking out contiguous sublists from an ascending sequence:

> groupBy (\a b -> a+1 == b) [1,2,3,4,6] [[1,2,3,4],[6]]

- Splitting a line at the start of each word:

> groupBy (\ c1 c2 -> isLetter c1 || not (isLetter c2)) "This is a line" ["This ","is ","a ","line"]

Since this more useful definition agrees with the Haskell 98 one on its specified domain, it should be a backwards-compatible replacement.

The same applies toSee:

- Libraries list on Data.List.groupBy with non-transitive equality predicate
- Implementation in utility-ht

## [edit] 4 groupOn and sortOn

Almost all uses ofor

Since this use is so common, it might be worthwhile to add separate functions for this:

sortOn :: Ord b => (a -> b) -> [a] -> [a] sortOn = sortBy . comparing

groupOn :: Eq b => (a -> b) -> [a] -> [[a]] groupOn f = groupBy ((==) `on` f)

That is,

groupOn' :: Eq b => (a -> b) -> [a] -> [[a]] groupOn' f = groupBy (\x y -> f x == f y)

The names could be better, the idea behind 'on' comes from the 'on' function.

See utility-ht package.

## [edit] 5 Indexing lists

- Find the index of a sublist in a list

findSublistIndex :: Eq a => [a] -> [a] -> Maybe Int findSublistIndex xss xs = findIndex (isPrefixOf xss) $ tails xs -- Examples findSublistIndex findSublistIndex [5,6] [1..] == Just 4 findSublistIndex "abbc" "abcabbc" == Just 3 findSublistIndex [2,1] [2,4..10] == Nothing