跳到主要內容

Notes of Haskell Learning

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)).

more on type class

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.

標籤：

留言

張貼留言

這個網誌中的熱門文章

得利油漆色卡編碼方式

得利油漆色卡編碼方式 類似 Munsell 色彩系統 ，編碼方式為 HUE LRV/CHROMA 例如 10GY 61/449 ( 色卡 ) 編碼數值 描述 10GY hue ，色輪上從 Y(ellow) 到 G(reen) 區分為 0 ~ 99 ，數值越小越靠近 Y，越大越靠近 G 61 LRV (Light Reflectance Value) 塗料反射光源的比率，數值從 0% ~ 100% ，越高越亮，反之越暗，也可理解為明度 449 chroma 可理解為彩度，數值沒有上限，越高顏色純度 (濃度) 越高 取決於測量儀器，對應至 RGB 並不保證視覺感受相同。 參考資料： 色卡對照網站 e-paint.co.uk Written with StackEdit .
張貼留言
閱讀完整內容

UTF8 與 Unicode 的轉換 (C++)

UTF8 與 Unicode 的轉換 (C++) 先釐清一下這兩者的性質 Unicode: 為世界上所有的文字系統制訂的標準，基本上就是給每個字(letter)一個編號 UTF-8: 為 unicode 的編號制定一個數位編碼方法 UTF-8 是一個長度介於 1~6 byte 的編碼，將 unicode 編號 (code point) 分為六個區間如下表 1 Bits First code point Last code point Bytes Byte 1 Byte 2 Byte 3 Byte 4 Byte 5 Byte 6 7 U+0000 U+007F 1 0xxxxxxx 11 U+0080 U+07FF 2 110xxxxx 10xxxxxx 16 U+0800 U+FFFF 3 1110xxxx 10xxxxxx 10xxxxxx 21 U+10000 U+1FFFFF 4 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx 26 U+200000 U+3FFFFFF 5 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 31 U+4000000 U+7FFFFFFF 6 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 觀察上面的表應該可以發現 除了 7 bits 的區間外，第一個 byte 開頭連續 1 的個數就是長度，例如 110XXXXX 就是 2 byte 長，而 1110xxxx 就是 3 byte 除了第一個 byte 外，之後的 byte 前兩個 bit 一定是 10 開頭，這樣的好處在於確立了編碼的 self-synchronizeing，意即當編碼為多個 byte 時，任取一個 byte 無法正常解碼。 Note 第一點中的例外 (7 bits) 是為了與 ASCII 的相容性，而第二點會影響到 code point 至 UTF-8 的轉換。 為了與 UTF-16 的相容性，在 R...
張貼留言
閱讀完整內容

C++17 新功能 try_emplace

C++17 新功能 try_emplace 回顧 emplace 大家的好朋友 Standard Template Library (STL) 容器提供如 push_back , insert 等介面，讓我們塞東西進去； C++11 之後，新增了 emplace 系列的介面，如 std::vector::emplace_back , std::map::emplace 等，差異在於 emplace 是在容器內 in-place 直接建構新元素，而不像 push_back 在傳遞參數前建構，下面用實例來說明： struct Value { // ctor1 Value ( int size ) : array ( new char [ size ] ) , size ( size ) { printf ( "ctor1: %d\n" , size ) ; } // ctor2 Value ( const Value & v ) : array ( new char [ v . size ] ) , size ( v . size ) { printf ( "ctor2: %d\n" , size ) ; memcpy ( array . get ( ) , v . array . get ( ) , size ) ; } private : std :: unique_ptr < char [ ] > array ; int size = 0 ; } ; struct Value 定義了自訂建構子 (ctor1)，以指定大小 size 配置陣列，複製建構子 (ctor2) 則會配置與來源相同大小及內容的陣列，為了方便觀察加了一些 printf 。當我們如下使用 std::vector::push_back 時 std :: vector < Value > v ; v . push_back ( Value ( 2048 ) ) ; 首先 Value 會先呼叫 ctor1，傳給 push_ba...
張貼留言
閱讀完整內容