Notes of Haskell Learning

References

List Comprehension

[(i,j)| i <- [0,1], j <- [1..6] ]
-- [(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6)]

Function

Function is consists of signature and definition.

Signature

fnName :: (TypeClass param1, ...) => param1 -> param2 -> ... -> result
--         ^^^^^^^^^^^^^^^^^^^^^^^ Constraints for the following function

Readit:

Function fnName is constrained by … and defined as a function takes a parameter param1 and returns (->)
a function (param2 -> ... -> result) which takes a parameter param2 and returns a function … and so on.

The -> is right associative. i.e.
param1 -> param2 -> ... -> result is equal to param1 -> (param2 -> (... -> result)).

Definition

Signature for a complete function is omitted below.

1. Bindings

fnName pattern1 = expr
fnName ref@pattern2 = expr ... ref
--                             ^^^ use the reference instead of pattern2
pattern1 `fnName` pattern2 = expr -- infix syntax

2. Guards

fnName paramAlias1 paramAlias2
    | condition = expr
    | otherwise = expr
    -- "where" binding
    where ref = expr'

ref appears in where clause can be used in condition and expr (but not in expr')

Note
We can use guards along with pattern matching as follows

fnName pattern1 = expr
fnName pattern2
    | condition = expr
    | otherwise = expr
    -- ...

e.g.

-- Get i-th element from a list where
-- i starts from 1
ith :: [a] -> Int -> a
ith (x:_) 1 = x
ith (_:xs) n
  | n < 1 = error "Out of bound"
  | otherwise = ith xs (n-1)

3. Expression: let … in …

fnName paramAlias1 paramAlias2
    let ref1 = expr
        ref2 = expr
    in  fn ref1 ref2

Difference between let and where are

let bindings are expressions themselves. where bindings are just syntactic constructs
let bindings can’t be used across guards

4. Expression: case … of …

fnName param = case expr of pattern -> result  
            pattern -> result  
            pattern -> result  
             ...

Higher Order Functions

Map

map is a function that apply given function to every element in a list.

map' :: (a -> b) -> [a] -> [b]
map' fn list
    | null list = [] -- edge condition
    | otherwise = fn x : map' fn xs
    where (x:xs) = list

Note: map is a built-in function

Filter

filter is a function that filter out elements in a list which evalueated to False by a given function.

filter' :: (a -> Bool) -> [a] -> [a]
filter' fn list
    | null list = []
    | fn x = x : filter' fn xs
    | otherwise = filter' fn xs
    where (x:xs) = list

Lambda

(\param1 param2 -> expr)

Fold

1. foldl (fold from left)

Type of foldl

foldl :: (a -> b -> a) -> a -> [b] -> a

(a -> b -> a) is a function that hold partial result
3rd a is initial value to be hold in above function
[b] is the list to be folded

sum' as an example:

sum' :: (Num a) => [a] -> a  
sum' xs = foldl (\partial x -> partial + x) 0 xs

2. foldr (fold from right)

Type of foldr

foldr :: (a -> b -> b) -> b -> [a] -> b

sum' as an example:

sum' :: (Num a) => [a] -> a  
sum' xs = foldr (\x partial -> x + partial) 0 xs

Note
the x and partial are swapped as of foldl.
foldl1 and foldr1 are two specialize version for non-empty lists.
scanl and scanr are similar to fold but collect partial result for each execution as a list.
foldl can NOT handle infinite list as foldr does.

Function Application: $

($) :: (a -> b) -> a -> b  
f $ x = f x

Function application with a space is left-associative (so f a b c is the same as ((f a) b) c))
function application with $ is right-associative.

f1 ( f2 p1 p2 )
-- is equal to
f1 $ f2 p1 p2

Module

Load Modules

In ghci:

ghci >:m moduleName

Import as:

import moduleName as alias

Import and check name collision, if so use period name (e.g. m.fn)

import qualified modulName

Import specific functions:

import moduleName (fnName, ...)

Import functions exclude specific ones:

import moduleName hiding (fnName, ...)

Create Modules

module mName
(fnName1,
 fnName2,
    ...
) where

-- fnImpl

mName can be consist of period, i.e.

module m.subM
(Type1, -- export type only, no value constructors
 Type2(..) -- export type and all its value constructors
 fn1, 
 fn2
) where

-- valueCtorImpl
-- fnImpl

See Also: Abstration
Question: Can we import a top level module name? (probabily not)

Algebraic Data Type

Synopsis

data MyType = ValueCtor1 ParamType1 ParamType2 | ValueCtor2 ... deriving(BaseType)

Note
1. MyType and ValueCtor can be the same (if we have single ValueCtor only?).
2. ghci use data constuctor instead of value constructor.

e.g.

data Point = Point Float Float deriving (Show)
data Shape = Circle Point Float | Rectangle Point Point deriving (Show)

Firstly, we define a data type Point and its value constructor. Secondly we define Shape and two value constructors Circle and Rectangel of Shape. All value ctors defined are deriving Show.

Abstraction

By define an auxiliary function and omit exporting value ctors, we get better abstration.

-- Export
module Shape
(Shape,
 auxBaseCircle,
 auxBaseRectangle
) where

-- Data types
data Point = Point Float Float deriving (Show)
data Shape = Circle Point Float | Rectangle Point Point deriving (Show)

-- Auxiliary functions
auxBaseCircle :: Float -> Shape
auxBaseCircle r = Circle $ (0, 0) r

auxBaseRect :: Float -> Float -> Shape  
auxBaseRect width height = Rectangle (Point 0 0) (Point width height)

Now clients can only create shapes from auxiliary functions.

Note
As noted in Create Modules section, we can export a type via Type or Type(..).

Native Classes

TODO Make it clear.

Record

data Person = Person { firstName :: String
                     , lastName :: String  
                     , age :: Int  
                     , height :: Float  
                     , phoneNumber :: String  
                     , flavor :: String  
                     } deriving (Show)

Along with a value ctor for Person, a seris of functions are created. e.g.

ghci> let guy = Person "Acer" "Yang" 0 0 "1234-123" "Haskell"
ghci> firstName guy
"Acer"

Better readability

ghci> let guy = Person {firstName = "Acer", lastName = "Yang", ... }

Type Parameter

Compare with value ctor:

data MyType = ValueCtor ParamType1 ParamType2 deriving(BaseType)
data (TypeClass typeParam, ...) => TypeCtor typeParam = Type1 | Type2 | ...
--   ^^^^^^^^^^^^^^^^^^^^^^^^^^ type constraints (see below)

e.g.

data Maybe t = Nothing | Just t
data (Ord k) => Map k v = ...  -- Don't add the type constraints in real code

Read it:
Maybe is a type constructor that constructs Nothing or Just t from a type parameter t.

In Practice
DO NOT add type constraints in data declaration, doing so will cause every functions deal with that type require to have the same type constraints.

Constructors Are Functions

If we define

data Maybe' t = Nothing | Just t

then

ghci> :t Just
Just :: t -> Maybe' t
ghci> :t Nothing
Nothing :: Maybe' t

Nothing and Just t are functions for constructing Maybe’.

Partial Specialization

data Either a b = Left a | Right b

ghci> Right 20  
Right 20  
ghci> Left "w00t"  
Left "w00t"  
ghci> :t Right 'a'  
Right 'a' :: Either a Char  
ghci> :t Left True  
Left True :: Either Bool b

A Generic Vector

data Vector a = Vector a a a deriving (Show)  

vplus :: (Num t) => Vector t -> Vector t -> Vector t  
(Vector i j k) `vplus` (Vector l m n) = Vector (i+l) (j+m) (k+n)  

vectMult :: (Num t) => Vector t -> t -> Vector t  
(Vector i j k) `vectMult` m = Vector (i*m) (j*m) (k*m)  

scalarMult :: (Num t) => Vector t -> Vector t -> t  
(Vector i j k) `scalarMult` (Vector l m n) = i*l + j*m + k*n

More-less a C++ equivalent

template<typename T>
struct Vector 
{ 
  Vector(T a, T b, T c) : x(a), y(b), z(c) {}
  // ignore other ctors for brievity
  T x,y,z;
};

template<typename T>
Vector<T> vplus(Vector<T> lhs, Vector<T> rhs)
{ 
  return Vector<T>{
    lhs.x + rhs.x, lhs.y + rhs.y, lhs.z + rhs.z
  }; 
}

Derived Instance

e.g. Native type class Eq requires two interfaces - == and /=. If a custom type class is deriving Eq, it must defines the those interfaces and we call the custom type is a derived instance of Eq.

1. Deriving Eq

data Person = Person { firstName :: String  -- declare type of firstName as String
                     , lastName :: String  
                     , age :: Int  
                     } deriving (Eq)

By deriving Eq, == and /= are defined implicitly which compare all parameters (firstName, lastName, and age) of Person’s value ctor.

2. Deriving Show

ghci> let mikeD = Person {firstName = "Michael", lastName = "Diamond", age = 43}  
ghci> mikeD  
Person {firstName = "Michael", lastName = "Diamond", age = 43}  
ghci> "mikeD is: " ++ show mikeD  
"mikeD is: Person {firstName = \"Michael\", lastName = \"Diamond\", age = 43}"

3. Deriving Read

ghci> read "Person {firstName =\"Michael\", lastName =\"Diamond\", age = 43}" :: Person  
Person {firstName = "Michael", lastName = "Diamond", age = 43}

4. Deriving Ord

data Bool = False | True deriving (Ord)

Note: Fields(value ctors without params) declared first is less than later ones. i.e. False < True

data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday   
           deriving (Eq, Ord, Show, Read, Bounded, Enum)

Enum’s interfaces: succ and pred.
Bounded’s interfaces: minBound and maxBound.

Thus

ghci> succ Monday  
Tuesday  
ghci> pred Saturday  
Friday  
ghci> [Thursday .. Sunday]  
[Thursday,Friday,Saturday,Sunday]  
ghci> [minBound .. maxBound] :: [Day]  
[Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday]

Type Synonyms

type TypeSynonyms = OriginType

e.g.

type String = [Char]
type AssocList k v = [(k, v)]

Partial applied type parameter

type IntAssocList = AssocList Int
type IntAssocList v = AssocList Int v -- write v or not are the same

Data Structure

1. List

Def

infixr 5 :-:  
data List a = Empty | a :-: (List a) deriving (Show, Read, Eq, Ord)

Usage

ghci> 3 :-: 4 :-: 5 :-: Empty  
(:-:) 3 ((:-:) 4 ((:-:) 5 Empty))

Note
infixr 5 :-: is fixity definition of :-: operator.

Define Type Class

A typeclass def.

class TypeClass typeVariable where
    fnName1 :: param -> ... -> ResultType
    fnName2 :: param -> ... -> ResultType
    pattern1 = expr1
    pattern2 = expr2

Function def can be omitted.

e.g.

class Eq a where  
    (==) :: a -> a -> Bool  
    (/=) :: a -> a -> Bool  
    x == y = not (x /= y)
    x /= y = not (x == y)

An algebraic data type

data TrafficLight = Red | Yellow | Green

Make the type as an instance of the typeclass

instance Eq TrafficLight where  
    Red == Red = True  
    Green == Green = True  
    Yellow == Yellow = True  
    _ == _ = False

The last line is a catch-all - pattern other than above are False.

Functor Type Class

class Functor f where  
    fmap :: (a -> b) -> f a -> f b

f is a type constructor.

instance Functor [] where  
    fmap = map

[] is a type constructor.

instance Functor Maybe where  
    fmap f (Just x) = Just (f x)  
    fmap f Nothing = Nothing

Surely Maybe is also a type constructor.

instance Functor (Either a) where  
    fmap f (Right x) = Right (f x)  
    fmap f (Left x) = Left x

Either a b is a type constructor which take 2 parameters which doesn’t fit into the Functor f’s definition.

Question Can we define a functor for Either? Is that useful?

Invert Pair’s Types

Original Q&A on Stackoverflow

C++

#include <utility>

template<typename Pair>
struct inv_pair
{
    typedef std::pair<
        typename Pair::second_type, 
        typename Pair::first_type
    > type;
};

Haskell

{-# LANGUAGE TypeFamilies #-}
type family Swap t 
type instance Swap (a,b) = (b,a)

type Pair_t1     = (Int, String)
type Inv_Pair_t1 = Swap Pair_t1

Written with StackEdit.

Acerlog 捨漏格

Notes of Haskell Learning

References

List Comprehension

Function

Signature

Definition

1. Bindings

2. Guards

3. Expression: let … in …

4. Expression: case … of …

Higher Order Functions

Map

Filter

Lambda

Fold

1. foldl (fold from left)

2. foldr (fold from right)

Function Application: $

Module

Load Modules

Create Modules

Algebraic Data Type

Synopsis

Abstraction

Native Classes

Record

Type Parameter

Constructors Are Functions

Partial Specialization

A Generic Vector

Derived Instance

1. Deriving Eq

2. Deriving Show

3. Deriving Read

4. Deriving Ord

Type Synonyms

Data Structure

1. List

Define Type Class

Functor Type Class

Invert Pair’s Types

標籤

留言

張貼留言