Prelude extensions
From HaskellWiki
(Difference between revisions)
Syntaxfree (Talk  contribs) 
m (Corrected type signature of mapSnd) 

(6 intermediate revisions by 4 users not shown)  
Line 1:  Line 1:  
__TOC__ 
__TOC__ 

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

−  
−  <haskell> 

−   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 

−  </haskell> 

−  
== Tuples == 
== Tuples == 

Line 41:  Line 11:  
  Apply a function to the second element of a pair 
  Apply a function to the second element of a pair 

−  mapSnd :: (b > c) > (a, b) > (c, b) 
+  mapSnd :: (b > c) > (a, b) > (a, c) 
mapSnd f (a, b) = (a, f b) 
mapSnd f (a, b) = (a, f b) 

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

−  == Matrix == 
+  === Treating pairs and lists in the same way === 
−  Sometimes you just want to multiply 2 matrices, like 
+  We can define a Pair class which allows us to process both pairs and nonempty lists using the same operator: 
−  [[1,2],[3,4]]*[[1,2],[3,4]] 
+  <haskell> 
+  import Control.Arrow ((***)) 

−  The following makes it possible, but requires fglasgowexts : 
+  infixl 4 <**> 
−  <haskell> 
+  class Pair p x y  p > x, p > y where 
−  instance Num a => Num [[a]] where 
+  toPair :: p > (x, y) 
−  (+) = zipWith (zipWith (+)) 
+  (<**>) :: (x > a > b) > (y > a) > p > b 
−  () = zipWith (zipWith ()) 
+  (<**>) f g = uncurry id . (f *** g) . toPair 
−  negate = map (map negate) 
+  
−  (*) x y = map (matrixXvector x) y 
+  instance Pair (a, b) a b where 
−  where 
+  toPair = id 
−  matrixXvector m v = foldl vectorsum (repeat 0) $ zipWith vectorXnumber m v 
+  
−  vectorXnumber v n = map (n*) v 
+  instance Pair [a] a [a] where 
−  vectorsum x y = zipWith (+) x y 
+  toPair l = (head l, tail l) 
</haskell> 
</haskell> 

−  Or, in a more elegant way: 
+  == Matrices == 
+  A simple representation of matrices is as lists of lists of numbers: 

<haskell> 
<haskell> 

−  import Data.List 
+  newtype Matrix a = Matrix [[a]] deriving (Eq, Show) 
−  +  </haskell> 

−  instance Num a => Num [[a]] where 
+  These matrices may be made an instance of <hask>Num</hask> 
−  (+) = zipWith (zipWith (+)) 
+  (though the definitions of <hask>abs</hask> and <hask>signum</hask> are just fillers): 
−  () = zipWith (zipWith ()) 
+  <haskell> 
−  negate = map (map negate) 
+  instance Num a => Num (Matrix a) where 
−  n * m = [ [ sum $ zipWith (*) v w  w < transpose n ]  v < m ] 
+  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 

+  </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> 

Line 111:  Line 82:  
sure' f = either' f f 
sure' f = either' f f 

</haskell> 
</haskell> 

+  
+  [[Category:Code]] 

+  
+  == See also == 

+  [[List function suggestions]] 
Latest revision as of 00:27, 27 September 2007
Contents 
[edit] 1 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) > (a, c) 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)
mapFst
mapSnd
><
mapPair
first
second
***
See also pointfree programming.
[edit] 1.1 Treating pairs and lists in the same way
We can define a Pair class which allows us to process both pairs and nonempty lists using the same operator:
import Control.Arrow ((***)) infixl 4 <**> class Pair p x y  p > x, p > y where toPair :: p > (x, y) (<**>) :: (x > a > b) > (y > a) > p > b (<**>) f g = uncurry id . (f *** g) . toPair instance Pair (a, b) a b where toPair = id instance Pair [a] a [a] where toPair l = (head l, tail l)
[edit] 2 Matrices
A simple representation of matrices is as lists of lists of numbers:
newtype Matrix a = Matrix [[a]] deriving (Eq, Show)
Num
abs
signum
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
fromInteger
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]
[edit] 3 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