-- Import all functions from Data.List (including intersperse)
import Data.List
-- Import isAlpha only, unqualified
import Data.Char (isAlpha)
-- Import isUpper only, qualified
import qualified Data.Char as C (isUpper)
spaced = intersperse ' ' "Haskell"
original = filter isAlpha spaced
initial = filter C.isUpper spaced
{-
spaced becomes "H a s k e l l"
original becomes "Haskell"
initial becomes "H"
-}
Notice single- and multi-line comments!
The $ operator is a convenience to avoid parenthesis
f $ a = f a
Prelude> negate (2 + 5)
-7
Prelude> negate $ 2 + 5
-7
Prelude> sum (map (^2) (filter even [1..100]))
171700
Prelude> sum $ map (^2) $ filter even [1..100]
171700
The dot operator (.) composes two functions
(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)
Prelude> odd = not . even
Prelude> :t odd
odd :: Integral a => a -> Bool
Prelude> :t even
even :: Integral a => a -> Bool
Prelude> :t not
not :: Bool -> Bool
Prelude> twice f = f . f
Prelude> twice (*2) 5
20
Composition is associative
f . (g . h) = (f . g) . h
Prelude> sumSqrEven ns = sum (map (^2) (filter even ns))
Prelude> sumSqrEven [1..100]
171700
Prelude> sumSqrEven' = sum . map (^2) . filter even
Prelude> sumSqrEven' [1..100]
171700
sumSqrEven' is in pointfree
style, the others are not
Prelude> sumSqrEven'' xs = sum $ map (^2) $ filter even xs
171700
Often tidier, focus on the functions rather than the data
countA xs = length $ filter (== 'a') xs
countA' = length . filter (== 'a')
fn x = ceiling (negate (tan (cos (max 50 x))))
fn' = ceiling . negate . tan . cos . max 50
sumSquareFilter f xs = sum $ map (^2) $ filter f xs
sumSquareFilter' f = sum . map (^2) . filter f
Construct new lists from existing lists
Prelude> [x ^ 2 | x <- [1..5]]
[1,4,9,16,25]
Prelude> [(x,y) | x <- [1,2,3], y <- "ab"]
[(1,'a'),(1,'b'),(2,'a'),(2,'b'),(3,'a'),(3,'b')]
Prelude> [(x,y) | y <- "ab", x <- [1,2,3]]
[(1,'a'),(2,'a'),(3,'a'),(1,'b'),(2,'b'),(3,'b')]
Prelude> [(x,y) | x <- [1,2,3], y <- [x..4]]
[(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4)]
Prelude> factors n = [x | x <- [1..n], n `mod` x == 0]
Prelude> factors 15
[1,3,5,15]
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)
product :: Num a => [a] -> a
product [] = 1
product (n:ns) = n * product ns
length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
| x <= y = x : y : ys
| otherwise = y : insert x ys
isort :: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)
zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys
Prelude> zip "haskell" [1..]
[('h',1),('a',2),('s',3),('k',4),('e',5),('l',6),('l',7)]
Encapsulate patterns of recursion
-- Older versions of GHC
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
-- GHC 7.10 and newer
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
Prelude> foldr (+) 0 [1,2,3]
6
Prelude> 1 + (2 + (3 + 0))
6
sum xs = foldr (+) 0 xs
sum = foldr (+) 0
Prelude> product = foldr (*) 1
Prelude> product [1..5]
120
Prelude> length = foldr (\_ n -> n + 1) 0
Prelude> length []
0
Prelude> length [1..100]
100
Prelude> any f = foldr (\x b -> f x || b) False
Prelude> any even []
False
Prelude> any even [1,3,5,6]
True
In a left fold, the operator associates to the left
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
Prelude> foldr (^) 0 [2,3,4]
8
Prelude> 2 ^ (3 ^ (4 ^ 0))
8
Prelude> foldl (^) 0 [2,3,4]
0
Prelude> ((0 ^ 2) ^ 3) ^ 4
0
Introduce a new name for an existing type
type Coordinate = Integer
type Position = (Coordinate, Coordinate)
pos :: Position
pos = (10, 7)
swap :: Position -> Position
swap (x, y) = (y, x)
Type declarations cannot be recursive
type Tree = (Int, [Tree])
Declare a completely new type
data Direction = North | South | East | West
move :: Direction -> Position -> Position
move North (x, y) = (x, y + 1)
move South (x, y) = (x, y - 1)
move East (x, y) = (x + 1, y)
move West (x, y) = (x - 1, y)
Prelude> move North (10,0)
(10,1)
Type and constructors must begin with capital letters
Constructors can also have arguments
data Shape = Circle Float | Rect Float Float
shape = Rect 10.5 8.2
area :: Shape -> Float
area (Circle r) = pi * r ^ 2
area (Rect h w) = h * w
Constructors are a special type of functions
Prelude> :t Circle
Circle :: Float -> Shape
Prelude> :t Rect
Rect :: Float -> Float -> Shape
data Maybe a = Nothing | Just a
safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv m n = Just (m `div` n)
safehead :: [a] -> Maybe a
safehead [] = Nothing
safehead xs = Just (head xs)
Prelude> safediv 10 3
Just 3
Prelude> safediv 10 0
Nothing
Prelude> safehead [1..]
Just 1
Prelude> safehead []
Nothing
data Tree a = Leaf | Node (Tree a) a (Tree a)
tree = Node (Node Leaf 3 (Node Leaf 4 Leaf))
5
(Node (Node Leaf 6 Leaf) 7 Leaf)
occurs :: Eq a => a -> Tree a -> Bool
occurs _ Leaf = False
occurs x (Node l y r) = x == y || occurs x l || occurs x r
Prelude> occurs 6 tree
True
Prelude> occurs 2 tree
False
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
{-# MINIMAL (==) | (/=) #-}
instance Eq a => Eq (Tree a) where
Leaf == Leaf = True
(Node a b c) == (Node d e f) = a == d && b == e && c == f
_ == _ = False
Prelude> tree = Node (Node Leaf 'a' Leaf) 'b' Leaf
Prelude> tree == Node Leaf 'b' Leaf
False
Prelude> tree /= Node (Node Leaf 'a' Leaf) 'b' Leaf
False
Some instances can be derived automatically
data Tree a = Leaf | Node (Tree a) a (Tree a)
deriving (Show, Eq, Ord)
Prelude> Leaf == Leaf
True
Prelude> Leaf < Node Leaf 'a' Leaf
True
Prelude> tree = Node Leaf 2 Leaf
Prelude> tree > Node Leaf 1 Leaf
True
Prelude> tree > Node (Node Leaf 0 Leaf) 1 Leaf
False
Prelude> print tree
Node Leaf 2 Leaf