Difference between revisions of "Prelude extensions"
m (added link to Prelude function suggestions) 
RossPaterson (talk  contribs) (make Matrix definition portable) 

Line 53:  Line 53:  
See also [[pointfreepointfree]] programming. 
See also [[pointfreepointfree]] programming. 

−  == 
+  == Matrices == 
−  
−  Sometimes you just want to multiply 2 matrices, like 

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

−  
−  The following makes it possible, but requires fglasgowexts : 

+  A simple representation of matrices is as lists of lists of numbers: 

<haskell> 
<haskell> 

⚫  
+  newtype Matrix a = Matrix [[a]] deriving (Eq, Show) 

⚫  
⚫  
−  negate = map (map negate) 

−  (*) 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 

</haskell> 
</haskell> 

−  
+  These matrices may be made an instance of <hask>Num</hask> 

−  Or, in a more elegant way: 

+  (though the definitions of <hask>abs</hask> and <hask>signum</hask> are just fillers): 

−  
<haskell> 
<haskell> 

−  import Data.List 

⚫  
−  
⚫  
−  instance Num a => Num [[a]] where 

⚫  
−  (+) = zipWith (zipWith (+)) 

+  Matrix as * Matrix bs = 

−  () = zipWith (zipWith ()) 

+  Matrix [[sum $ zipWith (*) a b  b < transpose bs]  a < as] 

−  negate = map (map negate) 
+  negate (Matrix as) = Matrix (map (map negate) as) 
−  +  fromInteger x = Matrix (iterate (0:) (fromInteger x : repeat 0)) 

+  abs m = m 

+  signum _ = 1 

+  </haskell> 

+  The <hask>fromInteger</hask> method builds an infinite matrix, but addition and subtraction work even with infinite matrices, and multiplication works as long as either the first matrix is of finite width or the second is of finite height. 

+  Applying the linear transformation defined by a matrix to a vector is 

+  <haskell> 

+  apply :: Num a => Matrix a > [a] > [a] 

+  apply (Matrix as) b = [sum (zipWith (*) a b)  a < as] 

</haskell> 
</haskell> 

Revision as of 22:34, 9 May 2007
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
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 pointfree programming.
Matrices
A simple representation of matrices is as lists of lists of numbers:
newtype Matrix a = Matrix [[a]] deriving (Eq, Show)
These matrices may be made an instance of Num
(though the definitions of abs
and signum
are just fillers):
instance Num a => Num (Matrix a) where
Matrix as + Matrix bs = Matrix (zipWith (zipWith (+)) as bs)
Matrix as  Matrix bs = Matrix (zipWith (zipWith ()) as bs)
Matrix as * Matrix bs =
Matrix [[sum $ zipWith (*) a b  b < transpose bs]  a < as]
negate (Matrix as) = Matrix (map (map negate) as)
fromInteger x = Matrix (iterate (0:) (fromInteger x : repeat 0))
abs m = m
signum _ = 1
The fromInteger
method builds an infinite matrix, but addition and subtraction work even with infinite matrices, and multiplication works as long as either the first matrix is of finite width or the second is of finite height.
Applying the linear transformation defined by a matrix to a vector is
apply :: Num a => Matrix a > [a] > [a]
apply (Matrix as) b = [sum (zipWith (*) a b)  a < as]
Data.Either extensions
import Data.Either
either', trigger, trigger_, switch :: (a > b) > (a > b) > Either a a > Either b b
either' f g (Left x) = Left (f x)
either' f g (Right x) = Right (g x)
trigger f g (Left x) = Left (f x)
trigger f g (Right x) = Left (g x)
trigger_ f g (Left x) = Right (f x)
trigger_ f g (Right x) = Right (g x)
switch f g (Left x) = Right (f x)
switch f g (Right x) = Left (g x)
sure :: (a>b) > Either a a > b
sure f = either f f
sure' :: (a>b) > Either a a > Either b b
sure' f = either' f f