Language.Syntactic.Sharing.Utils

Some utility functions used by the other modules

Difference lists

type DList a = [a] -> [a]

Difference list

empty :: DList a

Empty list

single :: a -> DList a

Singleton list

fromDList :: DList a -> [a]

Misc.

reindex :: (Integral a, Ix a) => [a] -> a -> a

Given a list is of unique natural numbers, returns a function that maps each number in is to a unique number in the range [0 .. length is-1]. The complexity is O(maximum is).

count

Arguments

:: Ix a

=> (a, a)

Upper and lower bound on the elements to be counted

-> [a]

Elements to be counted

-> Array a Int

Count the number of occurrences of each element in the list. The result is an array mapping each element to its number of occurrences.

fullPartition :: (a -> a -> Bool) -> [a] -> [[a]]

Partitions the list such that two elements are in the same sub-list if and only if they satisfy the equivalence check. The complexity is O(n^2).