Personal tools

Prelude extensions

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Add link to point-free programming wikipage)
Line 63: Line 63:
 
<haskell>
 
<haskell>
 
instance Num a => Num [[a]] where
 
instance Num a => Num [[a]] where
abs x = map (map abs) x
+
negate = map (map negate)
 
(+) x y = zipWith (zipWith (+)) x y
 
(+) x y = zipWith (zipWith (+)) x y
 
(*) x y = map (matrixXvector x) y
 
(*) x y = map (matrixXvector x) y
 
where
 
where
matrixXvector :: [[a]] -> [a] -> [a]
+
matrixXvector m v = foldl vectorsum (repeat 0) $ zipWith vectorXnumber m v
matrixXvector m v = foldl vectorsum [] $ zipWith vectorXnumber m v
 
vectorXnumber :: [a] -> a -> [a]
 
 
vectorXnumber v n = map (n*) v
 
vectorXnumber v n = map (n*) v
vectorsum :: [a] -> [a] -> [a]
 
vectorsum [] y = y
 
vectorsum x [] = x
 
 
vectorsum x y = zipWith (+) x y
 
vectorsum x y = zipWith (+) x y
  +
</haskell>
  +
  +
Or, as another option:
  +
  +
<haskell>
  +
import Data.List
  +
  +
instance Num a => Num [[a]] where
  +
(+) = zipWith (zipWith (+))
  +
(-) = zipWith (zipWith (-))
  +
negate = map (map negate)
  +
n * m = [ [ sum $ zipWith (*) v w | w <- transpose n ] | v <- m ]
 
</haskell>
 
</haskell>

Revision as of 14:24, 22 June 2006

Contents


1 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


2 Tuples

It is often necessary to apply functions to either the first or the second part of a pair. This is often considered a form of mapping (like map from Data.List).

 -- | Apply a function to the first element of a pair
 mapFst :: (a -> c) -> (a, b) -> (c, b)
 mapFst f (a, b) = (f a, b)
 
 -- | Apply a function to the second element of a pair
 mapSnd :: (b -> c) -> (a, b) -> (c, b)
 mapSnd f (a, b) = (a, f b)
 
 -- | Apply a function to both elements of a pair
 mapPair :: (a -> c, b -> d) -> (a, b) -> (c, d)
 mapPair (f, g) (a, b) = (f a, g b)
Data.Graph.Inductive.Query.Monad module (section Additional Graph Utilities) contains
mapFst
,
mapSnd
, and also a function
><
corresponding to
mapPair
. Another implementation of these functions in the standard libraries: using
first
,
second
,
***
arrow operations overloaded for functions (as special arrows), see Control.Arrow module, or Arrow HaskellWiki page.

See also point-free programming.

3 Matrix

Sometimes you just want to multiply 2 matrices, like

[[1,2],[3,4]]*[[1,2],[3,4]]

The following makes it possible, but requires -fglasgow-exts :

instance Num a => Num [[a]] where
  negate = map (map negate)
  (+)  x   y  = zipWith (zipWith (+)) x y
  (*)  x   y  = map (matrixXvector x) y
    where
      matrixXvector m v = foldl vectorsum (repeat 0) $ zipWith vectorXnumber m v
      vectorXnumber v n = map (n*) v
      vectorsum x  y = zipWith (+) x y

Or, as another option:

import Data.List
 
instance Num a => Num [[a]] where
    (+) = zipWith (zipWith (+))
    (-) = zipWith (zipWith (-))
    negate = map (map negate)
    n * m = [ [ sum $ zipWith (*) v w | w <- transpose n ] | v <- m ]