跳到主要內容

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 .
張貼留言
閱讀完整內容

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...
張貼留言
閱讀完整內容

Notes for C/C++ Programming

Notes for C/C++ Programming Notes for C/C++ Programming Off by One Error Prone # define LEN 128 char buf [ LEN ] = { 0 } ; // -1 for prevent missing NULL terminator // since strncpy doesn't preserve it for us. strncpy ( buf , something , sizeof ( buf ) - 1 ) ; // snprintf does preserve NULL terminator for us // i.e. actual size for placing characters is sizeof(buf) - 1 // but it takes extra time to parsing format snprintf ( buf , sizeof ( buf ) , something ) ; Bad things often happen when we mess with -1 or +1 to pointers point to continuous elements. Absorber # define LEN 128 char buf [ LEN + 1 ] = { 0 } ; // ^^^^ Always preserve 1 byte strncpy ( buf , somethin , sizeof ( buf ) ) ; Constant Correctness (C/C++) Bad void do_something ( char * dest , char * src ) ; struct MyList { void do_something ( std :: string & name ) ; } ; Reason : Will the name be modified by the lookup method? Will stat...
張貼留言
閱讀完整內容