Haskell
Haskell のコンパイラ
* type inference が２階直感主義論理に対応し、停止性が保証されない
* evaluation strategy : http://dev.stephendiehl.com/fun/005_evaluation.html
# infinite types
Why Infinite type is not intruduced in Haskell ?
~~~
λ> m x = x x
:1:10: error:
• Occurs check: cannot construct the infinite type: t ~ t -> t1
• In the first argument of 'x', namely 'x'
In the expression: x x
In an equation for 'm': m x = x x
• Relevant bindings include
x :: t -> t1 (bound at :1:3)
m :: (t -> t1) -> t1 (bound at :1:1)
~~~
* Not because `m m` is not typable.
* Not because if we allow infinite types it also allows `rank-2 polymorphism`.
* Answer : It allows `[T] = T ` which is quite ambiguous, and also dangerous.
* Ωコンビネータの定義の仕方 : https://stackoverflow.com/questions/33546004/is-it-possible-to-define-omega-combinator-λx-xx-in-modern-haskell
!!! Tip
Reference : https://www.quora.com/Why-doesnt-Haskell-implement-infinite-types
* Haskell では、Infinite type は導入されていない。
* 実用的には、99%は fix type で代用が効き、残りの1%を犠牲にしている。
* infinite type は、datatype として定義する場合のみに許される
## Infinite Types In OCaml
~~~
$ ocaml -rectypes
~~~
allows to use Infinite Types
# Either
The Problem
~~~
Either a ( Either b c ) ~~ Either (Either a b) c
~~~
* Possible Answer : https://hackage.haskell.org/package/extensible-0.8/docs/Data-Extensible-Sum.html
* Possible Answer : New Compiler
* e.g. Eilenberg-Zilber Category による、 Eilenberg Compiler
# Around Haskell 98
* [Mark P Jones] Haskell（Typing Haskell in Haskell)
https://web.cecs.pdx.edu/~mpj/thih/TypingHaskellInHaskell.html
# pattern synonym
https://www.schoolofhaskell.com/user/icelandj/Pattern%20synonyms
# newtype
newtype の仕様 ( Haskell 98 report 4.3.2 )
* constructor destructor の対称性（一対一）、
* フィールドと destructor を混同している表記のため、圏論er には、ちょっとつらい？？
* フィールドの隠蔽が可能 ( 先日の Role の話へとつづく )
* ⊥ に対する挙動が異なる。( destructor ⊥ は ⊥ ではない )
newtype の動機
* newtype は、ある型に対して、""" rename """" するために導入された。
* Age 型を Int 型とは区別しつつも、同じようなオブジェクトとして定義したいような状況
* そのため、ある一つの型と equivalence であるため、constructor / deconstructor の同型射によって、構成される。
# POPL 2011 -
## role
再生可能な型について ( role の導入（内部で同じデータ型のものを同値関係で割ったもの） ) ( Int ~~ Age )
https://www.seas.upenn.edu/~sweirich/papers/popl163af-weirich.pdf
role : https://downloads.haskell.org/~ghc/8.8.3/docs/html/users_guide/glasgow_exts.html#roles
role := type / representational equivalence
* Representational equivalent : runtime type equivalence
* Name equivalence : Treat named types as basic types. Therefore two type expressions are name equivalent if and only if they are identical, that is if they can be represented by the same syntax tree, with the same labels.
* Structural equivalence : Replace the named types by their definitions and recursively check the substituted trees.
Role can tune the equivance relation.
# Automaton in Haskell
https://blog.jle.im/entry/intro-to-machines-arrows-part-1-stream-and
?? mealy machine ?? cf. Auto type in Fun of functional programming (Chap 10)
練習問題「Auto 用の、型は合うこれこれの app を定義できるが外延性を満たさないことを示せ」
# Crypto
cryptohash-0.11.9
~~~ Haskell
stack install cryptohash-0.11.9
stack install bytestring
ghci --package bytestring --package-hiding cryptonite
λ> :m Crypto.Hash Data.ByteString Data.ByteString.Char8
λ> sha1 :: Data.ByteString.ByteString -> Digest SHA1; sha1 = hash
λ> sha1 $ Data.ByteString.Char8.pack "hello"
aaf4c61ddcc5e8a2dabede0f3b482cd9aea9434d
λ> show ( hash $ Data.ByteString.Char8.pack "hello" :: Digest SHA3_512)
"75d527c368f2efe848ecf6b073a36767800805e9eef2b1857d5f984f036eb6df891d75f72d9b154518c1cd58835286d1da9a38deba3de98b5a53e5ed78a84976"
~~~
# Extensions
## TemplateHaskell
~~~
--ddump-splices ## enables GHC compiler to output the code Template Haskell Generated
~~~
# openGL prerequisities
~~~
$ sudo pacman -S mesa glu freeglut
$ stack install GLUT
~~~
# continuation
What are continuations?
To dispel puzzlement, we will have a second look at an example from way back in the book, when we introduced the `($)` operator:
~~~hs
> map ($ 2) [(2*), (4*), (8*)]
[4,8,16]
> :t ($ 2)
($ 2) :: Num a => (a -> b) -> b
~~~
There is nothing out of ordinary about the expression above, except that it is a little quaint to write that instead of `map (*2) [2, 4, 8]`. The `($)` section makes the code appear backwards, as if we are applying a value to the functions rather than the other way around. And now, the catch: such an innocent-looking reversal is at heart of continuation passing style!
From a CPS perspective, `($ 2)` is a suspended computation: a function with general type `(a -> r) -> r` which, given another function as argument, produces a final result. The `a -> r` argument is the continuation; it specifies how the computation will be brought to a conclusion. In the example, the functions in the list are supplied as continuations via map, producing three distinct results. Note that suspended computations are largely interchangeable with plain values: `flip ($)` converts any value into a suspended computation, and passing id as its continuation gives back the original value.
from [Haskell wiki](https://en.wikibooks.org/wiki/Haskell/Continuation_passing_style)
# some note
## `newtype`
`newtype` is something like `data`
## Ambigous module name error
~~~
error: Ambigous module packages : cryptohash & cryptonite
~~~
~~~
λ> :set -hide-package cryptohash
λ> :m Crypto.Hash ...
~~~
or
~~~
{-# LANGUAGE PackageImports #-}
import "cryptonite" Crypto.Hash ...
~~~
# symbols
https://www.haskell.org/onlinereport/lexemes.html
From the haskell report, this is the syntax for allowed symbols:
~~~hs
special -> ( | ) | , | ; | [ | ] | `| { | }
symbol -> ascSymbol | uniSymbol < special | _ | : | " | '>
ascSymbol -> ! | # | $ | % | & | * | + | . | / | < | = | > | ? | @
\ | ^ | | | - | ~
uniSymbol -> any Unicode symbol or punctuation
~~~
So, symbols are ascii symbols or unicode symbols except from those in special `| _ | : | " | '`, which are reserved (here `a | b` means "it may be a or b", and `a` means "may be everything in a except b"). A few paragraphs below, the report gives the complete definition for haskell operators:
~~~hs
varsym -> ( symbol {symbol | :})
consym -> (: {symbol | :})
reservedop -> .. | : | :: | = | \ | | | <- | -> | @ | ~ | =>
~~~
Operator symbols are formed from one or more symbol characters, as defined above, and are lexically distinguished into two namespaces (Section 1.4):
An operator symbol starting with a colon is a constructor.
An operator symbol starting with any other character is an ordinary identifier.
Notice that a colon by itself, ":", is reserved solely for use as the Haskell list constructor; this makes its treatment uniform with other parts of list syntax, such as "[]" and "[a,b]".
Other than the special syntax for prefix negation, all operators are infix, although each infix operator can be used in a section to yield partially applied operators (see Section 3.5). All of the standard infix operators are just predefined symbols and may be rebound.
# crypto
## Ambigous module name error
When you encounter an error: Ambigous module packages : cryptohash & cryptonite;
~~~hs
λ> :set -hide-package cryptohash
~~~
then load the other;
~~~
λ> :m Crypto.Hash Crypto.Hash.Algorithms Data.ByteString
λ> hash (pack [61,32] ) :: Digest SHA3_512
100c57a0f4b09fb0a579510d08eb435804a81fad20e1d8bed29e8cfcecf3abd851d63fc81958ee93ef84f0385bae68697d41e0b7d7e0c23acf57deb3826cd07f
λ>
~~~
# hmatrix
HMatrix provides a functional interface to standard dense linear algebra (svd, eigenvalues, linear systems, etc.) based on the excellent and highly optimized `BLAS/LAPACK` libraries.
## intro
~~~sh
$ cabal(or stack) install hmatrix
$ ghci
> :m Numeric.LinearAlgebra.HMatrix
~~~
## Construct Matrix
~~~hs
> ident 3
(3 >< 3)
[ 1.0, 0.0, 0.0
, 0.0, 1.0, 0.0
, 0.0, 0.0, 1.0 ]
> a = (2 >< 2) ([1..] :: [Double]) -- declare `Double` explicitly
(2 >< 2)
[ 1.0, 2.0
, 3.0, 4.0 ]
~~~
## Basic Operators
~~~hs
> -- add
> a + a
(2 >< 2)
[ 2.0, 4.0
, 6.0, 8.0 ]
> -- mul
> a <> a
(2 >< 2)
[ 7.0, 10.0
, 15.0, 22.0 ]
> -- app
> v = vector [1,2]
> app a v -- [5.0, 11.0]
> -- toList
> v = vector [1,2] -- [1.0, 2.0]
> toList v !! 1 -- 2.0
> -- toLists
> toLists a -- [[1.0,2.0],[3.0,4.0]]
> -- getElement
> toLists a !! 1 !! 1 -- 4.0
~~~
# sandbox
sandbox
: make a box into `.cabal-sandbox` for independent cabal packages
~~~sh
$ mkdir SOE
$ cd SOE
$ cabal sandbox init # Create a new sandbox
$ cabal install gtk2hs-buildtools # Install
gtk2hs-buildtools inside sandbox
$ export PATH=".cabal-sandbox/bin:$PATH" # Add the binaries
## installed in (current directory's) sandbox to $PATH
$ cabal install gtk # linux Install gtk
$ cabal install gtk -fhave-quartz-gtk # OSX
~~~
# "Learn You A Great Haskell"
Learn You A Great Haskell is a good for some beginner who wants to seize the atomosphere of Haskell Programming. I think another book for better approach to Haskell is "Algebra of Programming" by Dr. Richard Bird, which defines Nats, Lists, then Trees .. and give good tutorial and exercise to Haskell's Data Structure.
Still, this might be a little difficult book for beginner, so I recommend type below in ghci interpreter, into which I read this book and interpret.
## I/O Monad
let's start with see how monad works.
~~~sh
$ cat baby.hs
doubleMe x = x + x
$
$ ghci
Prelude>>> getLine >>= readFile >>= putStrLn
baby.hs
doubleMe x = x + x
~~~
## Hello,World
### Basics
~~~hs
Plelude>>> -- :set prompt
Plelude>>> :set prompt "> "
>
> not (True && False) -- True
> div 92 10 -- 9 (prefix)
> 92 `div` 10 -- 9 (infix)
> :l baby.hs -- load baby.hs file
>
> -- if b then x else y
> absolute x = if x>0 then x else -x
> absolute (-100) -- 100
>
> -- /=
> True /= False -- logical not equal
>
> -- : (cons operator)
> a:b:c = "ghasshee" -- a:"g", b:"h", c:"asshee"
>
> -- succ/pred
> succ 8 -- 9
> pred 0 -- -1
>
> -- min/max
> min 5 6.3 -- 5.0
> max 5 9 -- 9
>
> -- cycle/repeat/take/replicate
> take 10 (cycle "ski") -- "skiskiskis"
> take 10 (repeat 5) -- [5,5,5,5,5,5,5,5,5,5]
> replicate 3 10 -- [10,10,10]
> replicate 3 "gh " -- ["gh ","gh ","gh "]
> repeat "apple " -- ["apple ","apple ", ...
>
> -- crazy range
> [1.0,3.0 .. 10.0] -- [1.0,3.0,5.0,7.0,9.0,11.0] maybe because 11.0 = 10.999..
>
> -- <- (in operator)
> [ x | x <- [10..20], x /= 13, x /= 15] -- [10,11,12,14,16,17,18,19,20]
>
> -- _ (wild card)
> length' xs = sum [1 | _ <- xs]
>
> -- Tuples
> (1,3)
> (3, 'a', "hello")
>
> -- fst/snd
> fst (5,3) -- 5
> snd ("Wow",False) -- False
>
> -- zip
> zip [1..5] ['a','b','c','d','e'] -- [(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e')]
> zip [1.. ] nouns -- [(1,"frog"),(2,"apple"),(3,"I")]
~~~
e.g.
~~~
> removeNonUpper st = [ c | c <- st, c `elem` ['A' .. 'Z']]
> removeNonUpper "Hello, World!" -- "HW"
>
> nouns = ["Frog", "I"]
> verbs = ["slept", "dropped"]
> [ noun++ " " ++verb++ "." | noun <-nouns, verb <-verbs ]
[ "Frog slept.", "Frog dropped.", "I slept.", "I dropped."]
>
> -- triples
> triples = [(a,b,c) | a <- [1..5], b <- [1..4], c<-[1..3]]
> triples -- [(1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),... ]
>
> -- solving equations
> triangleEdges = [(a,b,c) | a <- [1..10], b <- [1..10], c<-[1..10], a^2 + b^2 == c^2, a <= b]
> triangleEdges -- [(3,4,5),(6,8,10)]
~~~
### Believe the Type
~~~hs
> :t 'a' -- 'a' :: Char
> :t True -- True :: Bool
> :t "Hello" -- "Hello" :: [Char]
> :t (True, "Hello") -- (True, "Hello") :: (Bool, [Char])
> :t [[1,2],[1,4]] -- [[1,2],[1,4]] :: Num t => [[t]]
> :t 4 == 5 -- 4 == 5 :: Bool
~~~
~~~hs
> factorial :: Integer -> Integer;
> factorial n = product[1..n]
>
> circumference :: Float -> Float
> circumference r = 2 * pi * r
> circumference' :: Double -> Double
> circumference' r = 2 * pi * r
> circumference 1 -- 6.2831855
> circumference' 1 -- 6.283185307179586
>
~~~
~~~hs
> :t head -- head :: [a] -> a
> :t tail -- tail :: [a] -> [a]
~~~
### Function Definition
~~~hs
lucky :: Int -> String
lucky 7 = "LUCKY NUMBER 7" -- applied first
lucky _ = "Sorry, not 7" -- applied second
> lucky 5 -- "Sorry, not 7"
> lucky 7 -- "LUCKY NUMBER 7"
~~~
e.g.
~~~hs
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n-1)
> factorial 61 -- 3098476543630901248
> factorial 614 -- 0
addVectors :: (Double,Double) -> (Double,Double) -> (Double,Double);
addVectors a b = (fst a + fst b, snd a + snd b)
> addVectors (2, 10) (302.3 , pi) -- (304.3,13.141592653589793)
addVectors :: (Double,Double) -> (Double,Double) -> (Double,Double);
addVectors (x1,y1) (x2,y2) = (x1+x2 , y1+y2)
> addVectors (2, 10) (302.3 , pi) -- (304.3,13.141592653589793)
> :t addVectors -- addVectors :: (Double, Double) -> (Double, Double) -> (Double, Double)
~~~
## Class Constraint
### `Eq`
type of equal is;
~~~hs
> :t (==)
(==) :: Eq a => a -> a -> Bool -- type a is an instance of Eq class
~~~
see `Eq` class
~~~hs
> :info Eq
class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
~~~
Build `Eq` instance with `(==)` and `(/=)`;
~~~hs
> data F_ck = Zero | NaN
>
> -- Write below declaration in a line using `;` operator !!
instance Eq F_ck where
(==) Zero Zero = True
(==) _ _ = False
(/=) x y = not $ (==) x y
>
> NaN == NaN -- False
~~~
- Except `IO` class , All standard Haskell types can be instance of `Eq` class.
### `Ord` / `Show` / `Read`
- `Eq a => Ord a` : To be an `Ord` instance, the type must first be an `Eq` instance.
~~~hs
λ> :info Ord
class Eq a => Ord a where
compare :: a -> a -> Ordering
(<) :: a -> a -> Bool
(<=) :: a -> a -> Bool
(>) :: a -> a -> Bool
(>=) :: a -> a -> Bool
max :: a -> a -> a
min :: a -> a -> a
{-# MINIMAL compare | (<=) #-}
λ> :info Show
class Show a where
showsPrec :: Int -> a -> ShowS
show :: a -> String
showList :: [a] -> ShowS
{-# MINIMAL showsPrec | show #-} -- Defined in ‘GHC.Show’
λ> :info Read
class Read a where
readsPrec :: Int -> ReadS a
readList :: ReadS [a]
GHC.Read.readPrec :: Text.ParserCombinators.ReadPrec.ReadPrec a
GHC.Read.readListPrec :: Text.ParserCombinators.ReadPrec.ReadPrec [a]
{-# MINIMAL readsPrec | readPrec #-} -- Defined in ‘GHC.Read’
~~~
Read is a little comples
~~~
λ> :t read -- read :: Read a => String -> a
λ> :t readList -- readList :: Read a => ReadS [a]
λ> :info ReadS -- type ReadS a = String -> [(a, String)]
-- Defined in ‘Text.ParserCombinators.ReadP’
~~~
e.g.
~~~
> show 3 -- "3"
> show (3 == 1+2) -- "True"
>
> read "5" -- ! err
> read "5" :: Float -- 5.0
> read "5" :: Char -- err
> read "\"5\"" :: Char -- err
> read "'5'" :: Char -- '5'
> read "'5'" :: String -- err
> read "\"5\"" :: String -- "5"
> read "[1,2,3,4]" :: [Int] -- [1,2,3,4]
> read "(1, '3')" :: (Int, Char) -- (1,'3')
> read "[1,2,3,4]" ++ [3] -- [1,2,3,4,3]
> read "\"HELLO\"" ++ "!" -- "HELLO!"
~~~
### `Monad` / `Applicative` / `Functor`
~~~
λ> :info Monad
class Applicative m => Monad (m :: * -> *) where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a
fail :: String -> m a
{-# MINIMAL (>>=) #-}
λ> :info Applicative
class Functor f => Applicative (f :: * -> *) where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
(*>) :: f a -> f b -> f b
(<*) :: f a -> f b -> f a
{-# MINIMAL pure, (<*>) #-}
λ> :info Functor
class Functor (f :: * -> *) where
fmap :: (a -> b) -> f a -> f b
(<$) :: a -> f b -> f a
{-# MINIMAL fmap #-} -- Defined in ‘GHC.Base’
instance Monad (Either e) -- Defined in ‘Data.Either’
instance Monad [] -- Defined in ‘GHC.Base’
instance Monad Maybe -- Defined in ‘GHC.Base’
instance Monad IO -- Defined in ‘GHC.Base’
instance Monad ((->) r) -- Defined in ‘GHC.Base’
instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
instance Functor (Either a) -- Defined in ‘Data.Either’
instance Functor [] -- Defined in ‘GHC.Base’
instance Functor Maybe -- Defined in ‘GHC.Base’
instance Functor IO -- Defined in ‘GHC.Base’
instance Functor ((->) r) -- Defined in ‘GHC.Base’
instance Functor ((,) a) -- Defined in ‘GHC.Base’
~~~
### `Enum`
~~~
λ> :info Enum
class Enum a where
succ :: a -> a
pred :: a -> a
toEnum :: Int -> a
fromEnum :: a -> Int
enumFrom :: a -> [a]
enumFromThen :: a -> a -> [a]
enumFromTo :: a -> a -> [a]
enumFromThenTo :: a -> a -> a -> [a]
{-# MINIMAL toEnum, fromEnum #-} -- Defined in ‘GHC.Enum’
instance Enum Word -- Defined in ‘GHC.Enum’
instance Enum Ordering -- Defined in ‘GHC.Enum’
instance Enum Integer -- Defined in ‘GHC.Enum’
instance Enum Int -- Defined in ‘GHC.Enum’
instance Enum Char -- Defined in ‘GHC.Enum’
instance Enum Bool -- Defined in ‘GHC.Enum’
instance Enum () -- Defined in ‘GHC.Enum’
instance Enum Float -- Defined in ‘GHC.Float’
instance Enum Double -- Defined in ‘GHC.Float’
~~~
type Ordering
~~~
> :info Ordering -- data Ordering = LT | EQ | GT
> pred (pred GT) -- LT
> succ LT -- EQ
>
> -- other function
> :t compare -- compare :: Ord a => a -> a -> Ordering
> "Apple" `compare` "Zoo" -- LT
> "Apple" `compare` "Android" -- GT
> compare 5 (2+3) -- EQ
~~~
`..` used in Enum class
~~~
> :t
> ['a' .. '\n'] -- ""
> ['a' .. 'z'] -- "abcdefghijklmnopqrstuvwxyz"
> ['a' .. 'Z'] -- ""
> [LT .. GT] -- [LT,EQ,GT]
> [2,3 .. 10] -- [2,3,4,5,6,7,8,9,10]
~~~
### `Bounded`
~~~
λ> :info Bounded
class Bounded a where
minBound :: a
maxBound :: a
~~~
e.g.
~~~
> minBound :: Char -- '\NUL'
> maxBound :: Char -- '\1114111'
> minBound :: Int -- -9223372036854775808
> maxBound :: Int -- 9223372036854775807
> minBound :: Bool -- False
> maxBound :: Bool -- True
> maxBound :: String -- ! err
> maxBound :: Double -- ! err
>
> :t minBound -- minBound :: Bounded a => a
> maxBound :: (Bool, Int, Char) -- (True,9223372036854775807,'\1114111')
~~~
### `Num` / `Integral` / `Real`
~~~
λ> :info Num
class Num a where
(+) :: a -> a -> a
(-) :: a -> a -> a
(*) :: a -> a -> a
negate :: a -> a
abs :: a -> a
signum :: a -> a
fromInteger :: Integer -> a
{-# MINIMAL (+), (*), abs, signum, fromInteger, (negate | (-)) #-} -- Defined in ‘GHC.Num’
λ> :info Integral
class (Real a, Enum a) => Integral a where
quot :: a -> a -> a
rem :: a -> a -> a
div :: a -> a -> a
mod :: a -> a -> a
quotRem :: a -> a -> (a, a)
divMod :: a -> a -> (a, a)
toInteger :: a -> Integer
{-# MINIMAL quotRem, toInteger #-} -- Defined in ‘GHC.Real’
λ> :info Real
class (Num a, Ord a) => Real a where
toRational :: a -> Rational
{-# MINIMAL toRational #-} -- Defined in ‘GHC.Real’
~~~
~~~
instance Num Word -- Defined in ‘GHC.Num’
instance Num Integer -- Defined in ‘GHC.Num’
instance Num Int -- Defined in ‘GHC.Num’
instance Num Float -- Defined in ‘GHC.Float’
instance Num Double -- Defined in ‘GHC.Float’
instance Integral Word -- Defined in ‘GHC.Real’
instance Integral Integer -- Defined in ‘GHC.Real’
instance Integral Int -- Defined in ‘GHC.Real’
instance Real Word -- Defined in ‘GHC.Real’
instance Real Integer -- Defined in ‘GHC.Real’
instance Real Int -- Defined in ‘GHC.Real’
instance Real Float -- Defined in ‘GHC.Float’
instance Real Double -- Defined in ‘GHC.Float’
~~~
~~~
> :t fromIntegral -- fromIntegral :: (Num b, Integral a) => a -> b
> fromIntegral (length "HELLO") + 3.2 -- 8.2
~~~
## Higher Ordered Functions
### `foldl` / `foldr`
~~~
h 3(h 4(h 5(h 6 c))) -- foldr h c [3,4,5,6]
h(h(h(h c 3)4)5)6 -- foldl h c [3,4,5,6]
~~~
e.g.
~~~
> foldl (++) "a" ["b","c"] -- "abc"
> foldr (++) "a" ["b","c"] -- "bca"
> foldr (++) "" ["b","c"] -- "bc"
> foldl (++) "" ["b","c"] -- "bc"
> foldl (-) 0 [1..10] -- -55
> foldr (-) 0 [1..10] -- -5
>
> -- foldl1 / foldr1 h list -- do not need starting constant c
> foldl1 max [1,2,3] -- 3
> foldl1 (+) [1,2,3] -- 6
>
> -- and'
> and' = foldr (&&) True
> and' (repeat False) -- False -- Haskell can find how infinite sequence is !!!
~~~
### lambda expression / `flip`
~~~
> -- lambda expression
> (\x y-> (x - y) ^ x) 3 5 -- -8
>
> -- flip f x y = f y x
> flip (\x y-> (x - y) ^ x) 3 5 -- 32
> flip (-) 5 3 -- -2
> flip subtract 20 3 -- 17
~~~
### `scanl` / `scanr`
shows each step of the whole fold state transition
~~~
> scanl (+) 0 [1,2,3,4] -- [0,1,3,6,10]
> scanr (+) 0 [1,2,3,4] -- [10,9,7,4,0]
~~~
e.g.
~~~
> sqrtSums n = length (takeWhile (< n) (scanl1 (+) (map sqrt [1..]))) + 1
> sqrtSums 1000 -- 131
~~~
### `$` / `(.)`
~~~
($) :: (a -> b) -> a -> b
f $ x = f x
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
~~~
~~~
f $ g $ h i = f(g(h i))
(f.g.h) i = f(g(h i))
f g h i = ((f g)h)i
~~~
e.g.
~~~
fn x = ceiling (negate (tan (cos (max 50 x)))) -- normal style
fn = ceiling . negate . tan . cos . max 50 -- point-free style
~~~
## Modules
### import
e.g.1
~~~
-- hoge.hs
import Data.List
numUniques :: (Eq a) => [a] -> Int
numUniques = length . nub
wordNums :: String -> [(String, Int)]
wordNums = map (\ws -> (head ws , length ws)) . group .sort . words
isIn :: (Eq a) => [a] -> [a] -> Bool
needle `isIn` haystack = any (needle `isPrefixOf` ) (tails haystack)
>:l hoge
> numUniques [10,2,4,3,10,10] -- 4
~~~
e.g.2
~~~
{-- mod.hs
import Data.Char
encode :: Int -> String -> String
encode offset msg = map (\c -> chr $ ord c + offset) msg
--}
> :l mod
> encode 1 ghasshee -- "hibttiff"
> (decode 1 . encode 1 ) "ghasshee" -- "ghasshee"
> (decode 1 . encode 2 ) "ghasshee" -- "hibttiff"
~~~
### define a module
~~~
module Nat where
data Nat = Zero | Succ Nat
~~~
## List
~~~
nub :: Eq a => [a] -> [a] -- Defined in ‘base-4.8.1.0:Data.OldList’
any :: Foldable t => (a -> Bool) -> t a -> Bool -- Defined in ‘Data.Foldable’
sort :: Ord a => [a] -> [a] -- Defined in ‘base-4.8.1.0:Data.OldList’
group :: Eq a => [a] -> [[a]] -- Defined in ‘base-4.8.1.0:Data.OldList’
~~~
e.g.
~~~
> nub [1,2,3] -- [1,2,3]
> group [1,2,3,3,3,2] -- [[1],[2],[3,3,3],[2]]
> sort [1,2,3,3,3,2] -- [1,2,2,3,3,3]
> (group . sort) [1,2,3,3,3,2] -- [[1],[2,2],[3,3,3]]
> any (>4) [1,2,3] -- False
> any (>2.9) [1,2,3] -- True
> any (=='G') "Ghasshee" -- True
> any (\x -> x >5 && x < 10 )[1,4,11] -- Flase
~~~
## IO
~~~
> sequence $ ( map print [1,2,3] )
1
2
3
[(),(),()]
> mapM print [1,2,3]
1
2
3
[(),(),()]
> mapM_ print [1,2,3]
1
2
3
~~~
# Remove cabal
moving to Stack, you shall remove cabal once.
~~~
sudo rm -rf /Library/Frameworks/GHC.framework
sudo rm -rf /Library/Frameworks/HaskellPlatform.framework
sudo rm -rf /Library/Haskell
rm -rf .cabal
rm -rf .ghc
rm -rf ~/Library/Haskell
find /usr/bin /usr/local/bin -type l | \
xargs -If sh -c '/bin/echo -n f /; readlink f' | \
egrep '//Library/(Haskell|Frameworks/(GHC|HaskellPlatform).framework)' | \
cut -f 1 -d ' ' > /tmp/hs-bin-links
# review /tmp/hs-links
sudo rm `cat /tmp/hs-bin-links`
~~~
# Parallel and Concurrent Programing in Haskell
## introduction
haskell は lazy なので、
普通 return により強制執行されるまで、
全ての関数は執行されない。
haskell では return により執行される評価は、
ふつうシングルスレッドで処理してしまう。
そうならないようにするために seq しておきましょう
## seq
- `:sprint` : 変数を evaluate せずにそのまま出力する
- `seq ()` : 一番外側の関数だけを evaluate する
~~~
> x = 1+2 :: Int
> y = (x,x+1)
> z = swap y
>
> :sprint z -- z = _
>
> seq z () -- ()
> :sprint z -- z = (_,_)
> seq y () -- ()
> :sprint z -- z = (_,_)
> :sprint y -- y = (_,_)
>
> seq x () -- ()
> :sprint z -- z = (_,3)
> :sprint y -- y = (3,_)
>
> y -- (3,4)
> :sprint z -- z = (4,3)
~~~
Haskell is truely `lazy` !
~~~
> xs = map (+1) [1..10] :: [Int]
> :sprint xs -- xs = _
> seq xs () -- ()
> :sprint xs -- xs = _ : _
> seq xs () -- ()
> :sprint xs -- xs = _ : _
> length xs -- 10
> :sprint xs -- xs = [_,_,_,_,_,_,_,_,_,_]
> sum xs -- 65
> :sprint xs -- xs = [2,3,4,5,6,7,8,9,10,11]
~~~
## rpar & rseq
~~~
rpar :: a -> Eval a
rseq :: a -> Eval a
~~~
a : thunk : unevaluate computation
- `rpar` : says "My argument could be evaluated in parallel"
- `rseq` : says "Evaluate my argument and wait for the result"
Here,
Evaluation is to `weak head normal form`
~~~
runEval :: Eval a -> a
~~~
`runEval` evaluates thunk
: completely pure
## sudoku
~~~
import Sudoku
import Control.Exception
import System.Environment
import Data.Maybe
main :: IO ()
main = do
[f] <- getArgs -- (1)
file <- readFile f -- (2)
let puzzles = lines file -- (3)
solutions = map solve puzzles -- (4)
print (length (filter isJust solutions)) -- (5)
-->
~~~
1. get the name of the file
2. _
~~~
> :t readFile -- readFile :: FilePath -> IO String
> file <- readFile "sudoku1.hs"
import Sudoku\n
import Control.Exception\n
...
> :t lines
lines :: String -> [String]
> lines file
["import Sudoku",
"import Control.Exception",
"import System.Environment", ...
]
~~~
## myFunctions
removeN : remove '\n' from String
~~~
removeN :: [Char] -> [Char]
removeN s = [ x | x <- s, x /= '\n']
~~~
## threadscope
see [here](https://wiki.haskell.org/ThreadScope) for detail.
~~~
1. Install XQuartz (from web) and reboot.
2. Install the gtk library and dependencies
$ brew update && brew install glib cairo gtk gettext fontconfig
3. Build freetype by hand (download freetype-2.6 from official site)
$ tar -xzvf freetype-2.6.tar.gz && cd freetype-2.6
$ ./configure
$ make && sudo make install
$ gtk-demo
4. Install Haskell GTK
$ cabal install gtk2hs-buildtools
$ mkdir ~/.cabal/bin
$ ln -s ~/Library/Haskell/ghc-7.8.4/lib/gtk2hs-buildtools-0.13.0.4/bin ~/.cabal/bin
$ export PKG_CONFIG_PATH=/opt/X11/lib/pkgconfig
$ brew tap homebrew/versions
$ cabal install gtk -fhave-quartz-gtk
5. threadscope
$ cabal install threadscope
$ ln -s ~/Library/Haskell/ghc-7.8.4/lib/threadscope-0.2.7/bin/threadscope /usr/local/bin/
$ threadscope
~~~