✏️ 강의 필기

정나영·2022년 11월 6일
오픈소스 SW개발론
1

Lecture 2.

2.1 Recursion and Helper Functions

repeatString n str = repeatHelper n str ""

repeatHelper n str result = if (n==0)
                            then result
                            else repeatHelper (n-1) str (result++str)

Pattern Matching

--fibonacci numbers, slow version
fibonacci 1 = 1
fibonacci 2 = 1
fibonacci n = fibonacci(n-2) + fibonacci(n-1)
ex) fibonacci 5
==> fibonacci 3 + fibonacci 4
==> (fibonacci 1 + fibonacci 2) + fibonacci 4
==> (1+1) + fibonacci 4
==> (1+1) + (fibonacci 2 + fibonacci 3)
==> (1+1) + (fibonacci 2 + (fibonacci 1 + fibonacci 2))
==> (1+1) + (1+(1+1))
==> 5

Helper Functions

--fibonacci numbers, fast version
fibonacci :: Integer -> Integer
fibonacci n = fibonacci' 0 1 n

fibonacci' :: Integer -> Integer -> Integer -> Integer
fibonacci' a b 1 = b
fibonacci' a b n = fibonacci' b (a+b) (n-1)
ex) fibonacci 5
==> fibonacci' 0 1 5
==> fibonacci' 1 1 4
==> fibonacci' 1 2 3 
==> fibonacci' 2 3 2
==> fibonacci' 3 5 1 
==> 5

2.2 Guards

--definition--

f x y z
    | condition 1 = something
    | condition 2 = other
    | otherwise = somethingother

🧷 Guard와 Pattern Matching의 차이점

: Guard를 사용하면 임의의 코드를 그룹화하여 작성 가능,
Pattern matching은 패턴에 따라서 쭉 나열

--pattern matching

factorial :: Int -> Int
factorial 1 = 1
facotirla n = n * factorial(n-1)
--guards

factorial n 
    | n<0   = -1
    | n==0  = 1
    | otherwise = n * factorial(n-1)

🧷 Guard와 Pattern Matching 조합(combine) 가능

guessAge :: String -> Int -> String
guessAge "Griselda" age --pattern matching
    | age < 47 = "Too low!"
    | age > 47 = "Too high!"
    | otherwise = "Correct!"
guessAge "Hansel" age
    | age < 12 = "Too low!"
    | age > 12 = "Too high!"
    | otherwise = "Correct!"
guessAge name age = "Wrong name!"
ghci> guessAge "Griselda" 30
"Too low!"
ghci> guessAge "Griselda" 60
"Too high!"
ghci> guessAge "Griselda" 47
"Correct!"
ghci> guessAge "Bob" 30
"Wrong name!"
ghci> guessAge "Hansel" 10
"Too low!"

2.3 List

  • ⭐️ 리스트의 원소 타입은 동일해야한다 (homogeneous).
ghci> [0,3,4,1+1] :: [Int]
[0,3,4,2]
ghci> :t [True,True,False]
[True,True,False] :: [Bool]
ghci> :type ["Moi","Hei"]
["Moi","Hei"] :: [String]
ghci> :t []
[] :: [a] --a는 타입변수

ghci> :t [[1,2],[3,4]] :: [[Int]]
[[1,2],[3,4]] :: [[Int]] :: [[Int]]
ghci> [1..7] :: [Int]
[1,2,3,4,5,6,7]
ghci> :t [1..7] :: [Int]
[1..7] :: [Int] :: [Int]

List Operations

head :: [a] -> a -- returns the first element
tail :: [a] -> [a] -- returns everything except the first element
init :: [a] -> [a] -- returns evething except the last element
last :: [a] -> a --returns the last element
take :: Int -> [a] -> [a] -- returns the n first elements
drop :: Int -> [a] -> [a] -- returns everything except the n first elements
(++) :: [a] -> [a] -> [a] -- lists are catenated with the ++ operator
(!!) :: [a] -> Int -> a -- lists are indexed with the !! operator
reverse :: [a] -> [a] -- reverse a list
null :: [a] -> Bool -- is this list empty?
length :: [a] -> Int -- the length of a list
ghci> head [1,2,3,4,5]
1
ghci> tail [1,2,3,4,5]
[2,3,4,5]
ghci> init [1,2,3,4,5]
[1,2,3,4]
ghci> last [1,2,3,4,5]
5
ghci> take 3 [1,2,3,4,5]
[1,2,3]
ghci> take 100 [1,2,3,4,5]
[1,2,3,4,5]
ghci> drop 3 [1,2,3,4,5]
[4,5]
ghci> drop 100 [1,2,3,4,5]
[]
ghci> (++) [1,2,3] [4,5]
[1,2,3,4,5]
ghci> (!!) [1,2,3,4,5] 3
4
ghci> reverse [1,2,3,4,5]
[5,4,3,2,1]
ghci> null [1,2,3,4,5]
False
ghci> null []
True
ghci> length [1,2,3,4,5]
5
  • (==) 연산자를 사용하여 List를 비교할 수 있다. 
ghci> [1,2,3] == [1,2,3]
True
ghci> [1,2,3] == [3,1,2]
False
  • String은 list의 다른 이름이고, Char의 list이다([Char]).
ghci> :type "asdf"
"asdf" :: String
ghci> :type "asdf" :: [Char]
"asdf" :: [Char] :: [Char]
  • 이외의 다른 리스트 연산들은 Data.list module 사용
ghci> import Data.List
ghci> sort [5,3,2,4,1]
[1,2,3,4,5]
  • 리스트 연산 예제
ghci> [7,10,4,5] !! 2
4
ghci> f xs = take 2 xs ++ drop 4 xs
ghci> f [1,2,3,4,5,6]
[1,2,5,6]
ghci> f [1,2,3]
[1,2]
ghci> g xs = tail xs ++ [head xs] 
--head는 원소 하나를, tail은 list를 리턴하기 때문에 연산이 불가하여 타입을 맞춰준다.
ghci> g [1,2,3]
[2,3,1]
ghci>  it --제일 마지막 결과를 가리킴
[2,3,1]
ghci> g it
[3,1,2]

2.4 Immutability

ghci> list = [1,2,3,4]
ghci> reverse list
[4,3,2,1]
ghci> list
[1,2,3,4]
ghci> drop 2 list
[3,4]
ghci> list
[1,2,3,4]

-> list의 값은 변하지 않는다.t

2.5 Type Inference and Polymorphism

head :: [a] -> a
a : 타입 변수 (e.g. b,c,thisIsATypeVariable 모두 가능 -> 첫 글자 소문자)

ghci> :type [True,False]
[True,False] :: [Bool]
ghci> :type head
head :: [a] -> a
ghci> :type head [True,False]
head [True,False] :: Bool

ghci> :type tail
tail :: [a] -> [a]
ghci> tail [True,False]
[False]
ghci> :type tail [True,False]
tail [True,False] :: [Bool]
ghci> f xs ys = [head xs, head ys]
ghci> :type head
head :: [a] -> a
ghci> :type f
f :: [a] -> [a] -> [a]

ghci> g zs = f "Moi" zs
ghci> :type g
g :: [Char] -> [Char] --"Moi"가 [Char]이므로 두번째 리스트도 [Char]

  • 용어
    type parameter : 리스트 안에 들어오는 parameter로 지정한 타입
    parameterized type : parameter를 받는(가지고 있는) 타입
    polymorphism : 여러 종류 타입의 인자를 가질 수 있는 특성
    type variable : 타입 변수
    parametric polymorphism : 타입 변수를 사용하는 형태

  • Type Annotations (타입 주석)
    ex) guessAge :: String -> Int -> String
    타입 주석을 주는 것을 권장

2.6 The Maybe Type

Maybe 타입의 constructor(생성자) : Nothing, Just
함수 호출 시, 정상적인 경우와 비정상적인 경우 합쳐진 것을 리턴값으로 하고자 할 때, Maybe 타입 사용!
-> 정상적인 경우 Just a 리턴, 비정상적인 경우 Nothing

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

ghci> Nothing :: Maybe Bool
Nothing
ghci> Just False :: Maybe Bool
Just False
ghci> Just True :: Maybe Bool
Just True

ghci> Nothing :: Maybe Int
Nothing
ghci> Just 0 :: Maybe Int
Just 0
ghci> Just 1 :: Maybe Int
Just 1
ghci> Just (-1) :: Maybe Int
Just (-1)

ghci> Nothing :: Maybe [Int]
Nothing
ghci> Just [] :: Maybe [Int]
Just []
ghci> Just [1,2] :: Maybe [Int]
Just [1,2]

ghci> Just "a camel"
Just "a camel"
ghci> :t Just "a camel"
Just "a camel" :: Maybe String
ghci> Just True
Just True
ghci> :t Just True
Just True :: Maybe Bool
  • 리턴 값이 Maybe 타입
login :: String -> Maybe String
login "f4bulous!" = Just "unicon73"
login "swordfish" = Just "megahacker"
login _ = Nothing

ghci> login "nang"
Nothing
ghci> login "swordfish"
Just "megahacker"
  • 인자의 타입이 Maybe
    - pattern matching 이용
perhapsMultiply :: Int -> Maybe Int -> Int
perhapsMultiply i Nothing = i
perhapsMultiply i (Just j) = i*j

ghci> perhapsMultiply 3 (Just 2)
6
ghci> perhapsMultiply 3 Nothing
3
intOrZero :: Maybe Int -> Int
intOrZero Nothing = 0
intOrZero (Just i) = i

safeHead :: [a] -> Maybe a
safeHead xs = if null xs then Nothing else Just (head xs)
--head 함수는 빈 리스트가 인자로 오면 에러 발생
--safeHead 함수는 빈 리스트가 오면 Nothing 리턴

headOrZero :: [Int] -> Int
headOrZero xs = intOrZero (safeHead xs)

ghci> intOrZero (Just 5)
5
ghci> intOrZero Nothing
0
ghci> safeHead [1,2,3,4,5]
Just 1
ghci> safeHead []
Nothing
ghci> headOrZero []
0
ghci> headOrZero [1,2,3,4,5]
1
headOrZero [] => intOrZero (safeHead []) => intOrZero Nothing => 0
headOrZero [1] => intOrZero (safeHead [1]) => intOrZero (Just 1) => 1

2.7 Constructors (생성자)

  • Maybe 타입의 두가지 생성자 : Just, Nothing

  • 대문자로 시작

  • pattern matching 을 할 수 있다.

  • Nothing, True, False는 constructors 이면서 따로 인자를 받지 않으므로 constants (상수) 취급

ghci> :t Nothing
Nothing :: Maybe a
ghci> :t True
True :: Bool
ghci> :t False
False :: Bool
  • Just 는 인자가 필요하므로 함수인 것처럼 취급
ghci> :t Just
Just :: a -> Maybe a

2.8 The Either Type

  • Either 타입의 생성자 : Left, Right
    ->Left : a 타입의 인자, Right : b 타입의 인자를 취한다.

ghci> Left 0 :: Either Int Bool
Left 0
ghci> Right True :: Either Int Bool
Right True
ghci> Left "asdf" :: Either String [Int]
Left "asdf"
ghci> Right [1,2] :: Either String [Int]
Right [1,2]
readInt :: String -> Either String Int
readInt "0" = Right 0
readInt "1" = Right 1
readInt s = Left ("Unspported string: " ++ s)

ghci> readInt "0"
Right 0
ghci> readInt "1"
Right 1
ghci> readInt "5"
Left "Unspported string: 5"
iWantAString :: Either Int String -> String
iWantAString (Right str) = str
iWantAString (Left number) = show number

ghci> iWantAString (Right "abcd")
"abcd"
ghci> iWantAString (Left 5)
"5"
  • Either 타입을 사용하여 다른 타입의 인자를 같은 타입으로 맞춰서 리스트에 넣을 수 있다.
ghci> :type [Left 1, Right "foo", Left 2] :: [Either Int String]
[Left 1, Right "foo", Left 2] :: [Either Int String]
  :: [Either Int String]

2.9 The case-of Expression

case <value> of <pattern> -> <expression>
                <pattern> -> <expression>
describe :: Integer -> String
describe 0 = "zero"
describe 1 = "one"
describe 2 = "an even prime"
describe n = "the number " ++ show n

🟰

describe :: Integer -> String
describe n = case n of 0 -> "zero"
                       1 -> "one"
                       2 -> "an even prime"
                       n -> "the number " ++ show n
parseCountry :: String -> Maybe String
parseCountry "FI" = Just "Finland"
parseCountry "SE" = Just "Sweden"
parseCountry _ = Nothing

flyTo :: String -> String
flyTo countryCode = 
    case parseCountry countryCode of 
        Just country -> "You're flying to " ++ country
        Nothing -> "You're not flying anywhere"
 
ghci> flyTo "FI"
"You're flying to Finland"
ghci> flyTo "DE"
"You're not flying anywhere"
  • case-of 는 helper function 대체가 가능
sentenceType :: String -> String
sentenceType sentence = 
    case last sentence of '.' -> "statement"
                          '?' -> "question"
                          '!' -> "exclamation"
                          _   -> "not a sentence"
                          
sentenceType1 :: String -> String
sentenceType1 sentence = classify (last sentence)
    where classify '.' = "statement"
          classify '?' = "question"
          classify '!' = "exclamation"
          classify _   = "not a sentence"
          
ghci> sentenceType "This is Haskell."
"statement"
ghci> sentenceType1 "This is Haskell."
"statement"

🤔 언제 case-of 을 사용하나요?

1) 함수 호출 후 결과에 대해 pattern matching을 할 때

  • pattern matching
motivate :: String -> String
motivate "Monday" = "Have a nice week at work!"
motivate "Tuesday" = "You're one day closer to weekend!"
motivate "Wednesday" = "3 more days until the weekend!"
motivate "Thursday" = "2 more days until the weekend!"
motivate "Friday" = "1 more day until the weekend!"
motivate _ = "Relax! You don't need to work today!"
  • case - of
motivate :: String -> String
motivate day = case distanceToSunday day of
  6 -> "Have a nice week at work!"
  5 -> "You're one day closer to weekend!"
  n -> if n > 1
       then show (n - 1) ++ " more day(s) until the weekend!"
       else "Relax! You don't need to work today!"
  • guards
motivate :: String -> String
motivate day
    | n == 6 = "Have a nice week at work!"
    | n == 5 = "You're one day closer to weekend!"
    | n > 1 = show(n-1) ++ " more day(s) until weekend!"
    | otherwise = "Relax! You don't need to work today!"
    where n = distanceToSunday day

2) helper function을 여러 패턴 간 공유할 경우

  • 에러 발생
    - where의 square x는 circle 패턴에만 적용
area :: String -> Double -> Double
area "square" x = square x
area "circle" x = pi * square x
    where square x = x * x
  • 옳은 구문
area :: String -> Double -> Double
area shape x = case shape of
    "square" -> square x
    "circle" -> pi * square x
    where square x = x * x

3) 함수 이름을 여러 번 사용해야 하는 경우

distanceToSunday :: String -> Int
distanceToSunday "Monday"    = 6
distanceToSunday "Tuesday"   = 5
distanceToSunday "Wednesday" = 4
distanceToSunday "Thursday"  = 3
distanceToSunday "Friday"    = 2
distanceToSunday "Saturday"  = 1
distanceToSunday "Sunday"    = 0

🟰

distanceToSunday :: String -> Int
distanceToSunday d = case d of
    "Monday" -> 6
    "Tuesday" -> 5
    "Wednesday" -> 4
    "Thursday" -> 3
    "Friday" -> 2
    "Saturday" -> 1
    "Sunday" -> 0

2.10 Pattern Matching

  • defining a function
f :: Bool -> Maybe Int -> Int
f False Nothing = 1
f False _       = 2
f True (Just i) = i
f True Nothing  = 0
  • case - of
case number of 0 -> "zero"
               1 -> "one"
               _ -> "not zero or one"
  • 생성자의 value 값 추출
getElement :: Maybe Int -> [a] -> a
getElement (Just i) xs = xs !! i
getElement Nothing xs = last xs

ghci> getElement (Just 3) [1,2,3,4,5,6]
4
ghci> getElement Nothing [1,2,3,4,5,6]
6
  • 비교
    x==Nothing 과 같은 연산자를 항상 사용할 수 있는 것은 아님
    -> 따로 정의 해야하는 상황에서 pattern matching 사용

Lecture. 3

3.1 Functional Programming

In Haskell a function is a value

  • 다른 함수를 인자로 받을 수 있다. (Higher-order)
applyTo1 :: (Int -> Int) -> Int // 괄호 주의! 
applyTo1 f = f 1

addThree :: Int -> Int
addThree x = x + 3

{-
applyTo1 addThree
    ==> addThree 1
    ==> 1 + 3
    ==> 4
-}
  • Higher-order & polymorphic function
doTwice :: (a -> a) -> a -> a --첫번째 인자로 함수 받음 -> 고차원함수
doTwice f x = f (f x)

{-
doTwice addThree        a -> a = Int -> Int,  a = Int
    doTwice :: (Int -> Int) -> Int

==> addThree (addThree 1)
==> addThree 4
==> 7 
-}

makeCool :: String -> String
makeCool str = "WOW " ++ str ++ "!"

{-
doTwice makeCool "Haskell"
    a -> a = String -> String,  a = String
    a      = String          ,  a = String
    
    ==> makeCool (makeCool "Haskell")
    ==> makeCool "WOW Haskell!"
    ==> "WOW WOW Haskell!!"
-}

Functional Programming on Lists

  • 리스트를 다루는 대표적인 함수

1) map
map :: (a -> b) -> [a] -> [b]

ghci> map addThree [1,2,3]
[4,5,6]

{-
map :: (a -> b) -> [a] -> [b]
addThree :: Int -> Int

map addThree [1,2,3]

    a -> b  =  Int -> Int   a=Int, b=Int
    [a]     =  [Int]        a = Int

    map :: (Int -> Int) -> [Int] -> [Int]
    map addThree :: [Int] -> [Int]
-}

2) filter
filter :: (a -> Bool) -> [a] -> [a]

positive :: Int -> Bool
positive x = x > 0

ghci> filter positive [0,1,-1,3,-3]
[1,3]

{-
filter :: (a -> Bool) -> [a] -> [a]

filter positive [0,1,-1,3,-3]
    a -> Bool = Int -> Bool     a = Int
    [a]  = [Int]                a = Int

    filter :: (Int -> Bool) -> [Int] -> [Int]
    filter positive :: [Int] -> [Int]
-}
onlyPositive xs = filter positive xs
mapBooleans f = map f [False, True]

{-
filter :: (a -> Bool) -> [a] -> [a]
positive :: Int -> Bool               a = Int

onlyPositive :: [Int] -> [Int]
-}

{-
map :: (a -> b) -> [a] -> [b]
    [a] = [Bool]                      a = Bool
    map :: (Bool -> b) -> [Bool] -> [b]
mapBooleans :: (Bool -> b) -> [b]
-}

{-
mapBooleans :: (Bool -> b) -> [b]
not :: Bool -> Bool

mapBooleans not  :: [Bool]
    Bool -> b = Bool -> Bool          b = Bool

-}
wrapJust xs = map Just xs
{-
map :: (a -> b) -> [a] -> [b]
Just :: a -> Maybe a

map Just xs
    a -> b = a -> Maybe a             b = Maybe a
    map :: (a -> Maybe a) -> [a] -> [Maybe a]

wrapJust :: [a] -> [Maybe a]
-}

리스트 함수형 프로그래밍 예제

palindrome :: String -> Bool
palindrome str = str == reverse str

palindromes :: Int -> [String]
palindromes n = filter palindrome (map show [1..n])

ghci> palindromes 150
["1","2","3","4","5","6","7","8","9","11","22","33","44","55","66","77","88","99",
"101","111","121","131","141"]
countAwords :: String -> Int
countAwords string = length (filter startsWithA (words string))
--words :: String -> [String]
    where startsWithA s = head s == 'a'
    
ghci> countAwords "does anyone want an apple?"
3
import Data.List
tails :: [a] -> [[a]]

ghci> tails "echo"
["echo","cho","ho","o",""]
substringOfLength :: Int -> String -> [String]
substringOfLength n string = map shorten (tails string)
    where shorten s = take n s

ghci> substringOfLength 3 "hello"
["hel","ell","llo","lo","o",""]
whatFollows :: Char -> Int -> String -> [String]
whatFollows c k string = 
    map tail 
        (filter match (substringOfLength (k+1) string))
   where match sub = take 1 sub == [c]

ghci> whatFollows 'a' 2 "abracadabra"
["br","ca","da","br",""]

3.2 Partial Application (부분 적용)

: 함수의 인자를 부분적으로 받아 함수 호출

ghci> add a b = a + b
ghci> add 1 5
6
ghci> addThree = add 3
ghci> addThree 2
5
ghci> map addThree [1,2,3]
[4,5,6]
ghci> map (add 3) [1,2,3]
[4,5,6]
between :: Integer -> Integer -> Integer -> Bool
between low high x = x < high && x > low

ghci> between 3 7 5
True
ghci> between 3 6 9
False
ghci> (between 1 5) 2
True
ghci> let f = between 1 5 in f 2
True
ghci> map (between 1 3) [1,2,3]
[False,True,False]

cyrrying
: partial application을 가능하게 하는 방식

Integer -> Integer -> Integer -> Bool
 =   Integer -> (Integer -> Integer -> Bool)
 =   Integer -> ( Integer -> (Integer -> Bool) )

ghci> :t between 1 2 3
between 1 2 3 :: Bool
ghci> :t between 1 2
between 1 2 :: Integer -> Bool
ghci> :t between 1
between 1 :: Integer -> Integer -> Bool
ghci> :t between
between :: Integer -> Integer -> Integer -> Bool

sections

ghci> map (*2) [1,3,5,7,9]
[2,6,10,14,18]
ghci> map (+3) [1,3,5,7,9]
[4,6,8,10,12]
ghci> map (1/) [1,3,5,7,9]
[1.0,0.3333333333333333,0.2,0.14285714285714285,0.1111111111111111]
ghci> map (/2) [1,3,5,7,9]
[0.5,1.5,2.5,3.5,4.5]

3.3 Prefix and Infix Notations (전위와 중위 표기법)

  • Infix를 Prefix로 쓸 때에는 괄호 () 로 묶어주기
    다른 함수의 인자로 (+)를 넘길 때 유용!
ghci> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
ghci> zipWith (+) [0,2,5] [1,3,3]
[1,5,8]

ghci> 6 `div` 2
3
ghci> div 6 2
3
  • 역따옴표를 사용하여 함수를 Infix로 사용할 수 있음 (인자가 두개인 경우)
ghci> (+1) `map` [1,2,3] 
[2,3,4]

3.4 Lambdas (anonymous functions)

let big x = x > 7 in filter big [1,10,100]
🟰
filter (\x -> x > 7) [1,10,100]
ghci> (\x -> x*x) 3
9
ghci> (\x-> reverse x == x) "ABBA"
True
ghci> filter (\x->reverse x == x) ["ABBA","ACDC","otto","lothar","anna"]
["ABBA","otto","anna"]
ghci> (\x y -> x^2 + y^2) 2 3
13

3.5 . and $ Operators

(.) : 함수 조합
($) : 괄호 줄이기
=> 고차원 함수를 작성할 때 유용

1) (.)

(.) :: (b -> c) -> (a -> b) -> a -> c

(f.g) x ==> f (g x)

double x = 2 * x
quadruple = double . double
f = quadruple . (+1)
g = (+1) . quadruple
third = head . tail. tail

doTwice f = f.f
let ttail = doTwice tail
ghci> ttail [1,2,3,4]
[3,4]
ghci> (doTwice tail) [1,2,3,4]
[3,4]

ghci> notEmpty x = not (null x)
ghci> filter notEmpty [[1,2,3],[],[4]]
[[1,2,3],[4]]
🟰
ghci> filter (not . null) [[1,2,3],[],[4]]
[[1,2,3],[4]]

2) ($)

($) :: (a -> b) -> a -> b

ghci> head (reverse "abcd")
'd'
🟰
ghci> head $ reverse "abcd"
'd'
ghci> reverse (map head (map reverse (["Haskell","pro"] ++ ["dodo","lyric"])))
"cool"
ghci> (reverse . map head . map reverse) (["Haskell","pro"] ++ ["dodo","lyric"])
"cool"
ghci>  reverse . map head . map reverse $ ["Haskell","pro"] ++ ["dodo","lyric"]
"cool"
map ($ "string") [reverse, take 2, drop 2]
    ==> [reverse $ "string", take 2 "string", drop 2 "string"]
    ==> ["gnirts","st","ring"]

3.6 whatFollows 함수 다시 작성해보기

3.7 리스트를 다루는 함수형 프로그래밍 예제

takeWhile even [2,4,1,2,3] ==> [2,4]
dropWhile even [2,5,1,2,4] ==> [5,1,2,4]

--리스트 포함 여부
elem 3 [1,2,3] ==> True 
elem 4 [1,2,3] ==> False
findSubstring :: String -> String -> String
findSubstring chars = takeWhile (\x -> elem x chars)
                        . dropWhile (\x -> not $ elem x chars)
                        
ghci> findSubstring "a" "bbaabaaaab"
"aa"
ghci> findSubstring "abcd" "xxxyyyzabaaxxabcd"
"abaa"
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith (++) ["John", "Mary"]["Smith","Cooper"]
	==> ["JohnSmith","MaryCooper"]
zipWith take [4,3] ["Hello","Warden"]
	==> ["Hell","War"]
id :: a -> a
filter id [True,False,True,True]
	==> [True,True,True]
dropWhile id [True,True,False,True,False]
	==> [False,True,False]

3.8 리스트와 재귀

  • data constructor : (:), []
ghci> :t (:)
(:) :: a -> [a] -> [a]
ghci> [1]
[1]
ghci> 1 : []
[1]
ghci> 1 : [2,3]
[1,2,3]
ghci> tail (1 : [2,3])
[2,3]
ghci> head (1 : [2,3])
1

리스트 만들기 

descend 0 = []
descend n = n : descend (n-1)

ghci> descend 4
[4,3,2,1]
let xs = "terve"
in _iterate tail (length xs) xs

==> ["terve","erve","rve","ve","e",""]
split :: Char -> String -> [String]
split c [] = []
split c xs = start : split c (drop 1 rest)
  where start = takeWhile (/=c) xs
        rest = dropWhile (/=c) xs
        
ghci> split 'x' "fooxxbarxquux"
["foo","","bar","quu"]

리스트 패턴매칭 

myhead :: [Int] -> Int
myhead [] = -1
myhead (first : rest) = first

mytail :: [Int] -> [Int]
mytail [] = []
mytail (first : rest) = rest

ghci> myhead [3,5,7,9]
3
ghci> mytail [1,2,3,4,5]
[2,3,4,5]
  • nest pattern
sumFirstTwo :: [Integer] -> Integer
sumFirstTwo (a:b:_) = a+b
sumFirstTwo _ = 0

ghci> sumFirstTwo []
0
ghci> sumFirstTwo [1]
0
ghci> sumFirstTwo [1,2]
3
ghci> sumFirstTwo [1,2,4]
3
describeList :: [Int] -> String
describeList (x:y:z:xs) = "a list with at least three elements"
describeList (x:y:[])   = "a list with two elements"
describeList (x:[])     = "a list with one element"
describeList []         = "an empty list"

ghci> describeList [1,3]
"a list with two elements"
ghci> describeList [1,2,3,4,5]
"a list with at least three elements"
ghci> describeList []
"an empty list"

❗️ x : y: z : [] = [x,y,z]

startsWithZero :: [Integer] -> Bool
startsWithZero (0:xs) = True
startsWithZero (1:xs) = False
startsWithZero []     = False

ghci> startsWithZero [1,3,5]
False
ghci> startsWithZero []
False
ghci> startsWithZero [0,1,2]
True

리스트 사용하기 

sumNumbers :: [Int] -> Int
sumNumbers [] = 0
sumNumbers (x : xs) = x + sumNumbers xs

ghci> sumNumbers [1,2,3]
6
--myMaximum의 인자는 하나이므로 재귀함수 방식으로 반복할 수는 없음 => 로컬함수 go 사용 (helper function)
myMaximum :: [Int] -> Int
myMaximum [] = 0
myMaximum (x : xs) = go x xs
    where go biggest [] = biggest
          go biggest (x:xs) = go (max biggest x) xs

ghci> myMaximum [-5,3,100,99,9999]
9999
countNothings :: [Maybe a] -> Int
countNothings [] = 0
countNothings (Nothing : xs ) = 1 + countNothings xs
countNothings (Just _ : xs) = countNothings xs

ghci> countNothings [Nothing, Just 1, Nothing]
2

리스트 만들고 사용하기 

doubleList :: [Int] -> [Int]
doubleList [] = []
doubleList (x:xs) = 2*x : doubleList xs

doubleList [1,2,3]
== doubleList ( 1 : ( 2 : ( 3 : [] )))
==> 2*1 : doubleList (2:(3:[]))
==> 2*1 : (2*2 : doubleList (3:[]))
==> 2*1 : (2*2 : (2*3 : doubleList []))
==> 2*1 : 2*2 : 2*3 : []
==> [2*1,2*2,2*3]
==> [2,4,6]
  • map
map :: (a->b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
  • filter
filter :: (a->Bool) -> [a] -> [a]
filter _pred [] = []
filter pred (x:xs)
    | pred x        = x : filter pred xs
    | otherwise     = filter pred xs

꼬리 재귀와 리스트

  • tail recursion : 재귀함수의 위치가 맨 마지막인 경우
    (돌아오더라도 특별히 실행할 것이 없는 경우를 말한다.)
-- Not tail recursive
sumNumbers :: [Int] -> Int
sumNumbers [] = 0
sumNumbers (x:xs) = x + sumNumbers xs
-- Tail recursive version
sumNumbers :: [Int] -> Int
sumNumbers xs = go 0 xs
    where go sum [] = sum
          go sum (x:xs) = go (sum+x) xs

ghci> sumNumbers [1,3,5,7,9]
25

3.9 리스트 제시법

  • Mapping
ghci> [2*i | i <- [1,2,3]]
[2,4,6]
ghci> map (2*) [1,2,3]
[2,4,6]
  • Filtering 
ghci> [i| i<- [1..7], even i]
[2,4,6]
ghci> filter even [1..7]
[2,4,6]
  • Mapping + Filtering
ghci> [2*i | i<-[1..7],even i]
[4,8,12]
ghci> map (2*) (filter even [1..7])
[4,8,12]
  • more example
[first ++ " " ++ last | first <- ["John", "Mary"], last <- ["Smith", "Cooper"]]
==> ["John Smith","John Cooper","Mary Smith","Mary Cooper"]
[reversed | word <- ["this","is","a","string"], let reversed = reverse word]
==> ["siht","si","a","gnirts"]
🟰
[reverse word | word <- ["this","is","a","string"]]
==> ["siht","si","a","gnirts"]
firstLetters string = [char | (char:_) <- words string]

ghci> firstLetters "Hello World!"
"HW"

3.10 Custom Operators (자신의 연산자 만들기)

(<+>) :: [Int] -> [Int] -> [Int]
xs <+> ys = zipWith (+) xs ys

ghci> [1,2,3] <+> [4,5,6]
[5,7,9]
ghci> zipWith (+) [1,2,3] [4,5,6]
[5,7,9]
(+++) :: String -> String -> String
a +++ b = a ++ " " ++ b

ghci> (+++) "Hello" "World!"
"Hello World!"
ghci> "Hello" ++ " " ++ "World!"
"Hello World!"

Lecture. 4

4.1 Tuple

fst :: (a, b) -> a
snd :: (a, b) -> b
zip :: [a] -> [b] -> [(a, b)]    
unzip :: [(a, b)] -> ([a], [b])  
partition :: (a -> Bool) -> [a] -> ([a], [a])

ghci> zip [1,2,3] [True,False,True]
[(1,True),(2,False),(3,True)]

ghci> unzip [("Fred",1),("Jack",10),("Helon",13)]
(["Fred","Jack","Helon"],[1,10,13])

ghci> partition (>0) [-1,1,-4,3,2,0]
([1,3,2],[-1,-4,0])
swap :: (a,b) -> (b,a)
swap (x,y) = (y,x)

ghci> swap (1, True)
(True,1)
  • 튜플에 대한 패턴매칭이 가능하다.
sumIf :: [(Bool, Int)] -> Int
sumIf [] = 0
sumIf ((True, x) : xs) = x + sumIf xs
sumIf ((False,_) : xs) = sumIf xs

ghci> sumIf [(True,1),(False,10),(True,100)]
101

4.2 Folding (접기)

sumNumbers :: [Int] -> Int
sumNumbers [] = 0
sumNumbers (x:xs) = x + sumNumbers xs

myMaximum :: [Int] -> Int
myMaximum [] = 0
myMaximum (x:xs) = go x xs
  where go biggest [] = biggest
        go biggest (x:xs) = go (max biggest x) xs

countNothings :: [Maybe a] -> Int
countNothings [] = 0
countNothings (Nothing : xs) = 1 + countNothings xs
countNothings (Just _  : xs) = countNothings xs

위 세 함수의 공통점

  • 인자로 리스트를 취한다.
  • 최종 결과는 인자로 주어진 리스트의 원소들의 값에 의존한다.
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f y []     = y
foldr f y (x:xs) = f x (foldr f y xs)
  • foldr 을 가지고 위 세 함수를 재작성할 수 있다.
--sumNumbers
foldr (+) 0 [1,2,3] ==> foldr (+) 0 (1:2:3:[])
                    ==> 1 + (foldr (+) 0 (2:3:[]))
                    ==> 1 + (2 + (foldr (+) 0 (3:[])))
                    ==> 1 + (2 + (3 + (foldr (+) 0 [])))
                    ==> 1 + (2 + (3 + 0))
map g xs = foldr helper [] xs
  where helper y ys = g y : ys

4.3 Type Classes (타입 클래스)

  • 타입들의 집합
  • 이 타입들에 사용할 수 있는 동일한 이름의 함수가 있어야 함 (ex . ==, +)

다형성 (polymorphism)

  • a -> a
    : a에 아무 조건이 없는 다형성 (parametric polymorphism)
  • Num a => a -> a -> a ->
    : a에 올 수 있는 타입은 Num 타입 클래스에 속함 (ad-hoc polymorphism)(overloading)

4.4 Type Constraints (타입 제약)

f :: (Eq a) => (a -> a) -> a -> Bool
f g x = x == g x
bothPairsEqual :: (Eq a, Eq b) => a -> a -> b -> b -> Bool
bothPairsEqual left1 left2 right1 right2 = left1 == left2 && right1 == right2

4.5 Standard Type Classes

Eq

(==) :: Eq a => a -> a -> Bool
(/=) :: Eq a => a -> a -> Bool
ghci> import Data.List
ghci> :t nub		-- 중복 제거
nub :: Eq a => [a] -> [a]
ghci> nub [3,5,3,1,1]
[3,5,1]
ghci> nub [[1,2],[3],[2,1],[1,2]]
[[1,2],[3],[2,1]]

Ord

compare :: Ord a => a -> a -> Ordering
(<) :: Ord a => a -> a -> Bool
(>) :: Ord a => a -> a -> Bool
(>=) :: Ord a => a -> a -> Bool
(<=) :: Ord a => a -> a -> Bool
max :: Ord a => a -> a -> a
min :: Ord a => a -> a -> a
ghci> compare 1 1 	
EQ						--Equal
ghci> compare 1 3
LT						--Less Than
ghci> compare 1 0
GT						--Greater Than
ghci> compare 'a' 'z'
LT
ghci> compare 'b' 'B'
GT
ghci> min 5 3
3
ghci> max 5 3
5
ghci> "nang" > "dang"
True
ghci> :t EQ
EQ :: Ordering

ghci> [1,2,3] > [2,5]	-- 맨 첫 원소부터 비교 (string과 동일한 방식)
False
ghci> [1,2,3] < [1,2,4]
True
import Data.List
sort :: Ord a => [a] -> [a]

ghci> sort [6,1,4,8,2]
[1,2,4,6,8]
ghci> sort "black sphinx of quartz, judge my vow!"
"      !,aabcdefghijklmnoopqrstuuvwxyz"
ghci> ' ' < 'a'
True
ghci> '!' < 'a'
True
import Data.List

comparing :: (Ord a) => (b -> a) -> b -> b -> Ordering
comparing f x y = compare (f x) (f  y)

sortByLength :: [[a]] -> [[a]]
sortByLength = sortBy (comparing length)

ghci> sortByLength [[1,2,3],[4,5],[4,5,6,7]]
[[4,5],[1,2,3],[4,5,6,7]]

Num, Integral, Factional, Floating

  • Num : 정수의 산술식에 대한 연산자, 함수를 지원하는 타입들
(+) :: Num a => a -> a -> a
(-) :: Num a => a -> a -> a
(*) :: Num a => a -> a -> a
negate :: Num a => a -> a    -- 음수로 바꿈
abs :: Num a => a -> a       -- 절댓값
signum :: Num a => a -> a    -- 부호 구하기 (-1, 0, +1 리턴)
fromInteger :: Num a => Integer -> a
(+) :: Num a => a -> a -> a

ghci> :t 123
123 :: Num p => p

ghci> 123 :: Double
123.0
ghci> 123 :: Int
123
ghci> 123 :: Integer
123
ghci> 123 :: Float
123.0

fromIntegral :: (Integral a, Num b) => a -> b

ghci> fromIntegral 3 
3
ghci> fromIntegral 3 :: Double
3.0
  • Integral
    - Integral의 타입들은 모두 Num 타입에 속한다.
div :: Integral a => a -> a -> a
mod :: Integral a => a -> a -> a

ghci> :t 123 `div` 5
123 `div` 5 :: Integral a => a
ghci> :t (123 `div` 5) :: Int
(123 `div` 5) :: Int :: Int
ghci> :t (123 `div` 5) :: Integer
(123 `div` 5) :: Integer :: Integer
  • Fractional
    - Fractional의 타입들은 모두 Num 타입에 속한다.
(/) :: Fractional a => a -> a -> a

ghci> :t 123 / 5
123 / 5 :: Fractional a => a

ghci> :t 123 `div` 5
123 `div` 5 :: Integral a => a
  • Floationg
    - Floating에 속하는 타입들은 Fractional 타입에 속한다. (Num 타입에도 속함)
sqrt :: Floating a => a -> a
sin :: Floating a => a -> a

ghci> :t (sqrt 2) :: Double
(sqrt 2) :: Double :: Double
ghci> :t (sqrt 2) :: Float
(sqrt 2) :: Float :: Float

Read and Show 

show :: Show a => a -> String
read :: Read a => String -> a
ghci> show 3
"3"
ghci> read "3" :: Int 	--타입 지정 해줘야함 (문자열을 읽어서 어떤 타입으로 바꿀지)
3
ghci> read "3" :: Double
3.0
ghci> show [1,2,3]
"[1,2,3]"
ghci> read "[1,2,3]" :: [Int] 
[1,2,3]

Foldable 

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
length :: Foldable t => t a -> Int

foldr (+) 1 Nothing   ==> 1
foldr (+) 1 (Just 3)  ==> 4
length Nothing        ==> 0
length (Just 'a')     ==> 1

🤔 타입클래스에 속한 연산자, 함수를 알아내고 싶을 때는 어떻게 하나요?
:info (타입클래스)

ghci> :info Num
type Num :: * -> Constraint
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’
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’

4.6 More Data Structures

Data.Map
import qualified Data.Map as Map

ghci> values = Map.fromList [("z",3),("w",4)]
ghci> values
fromList [("w",4),("z",3)]
ghci> Map.lookup "z" values
Just 3
ghci> Map.lookup "banana" values
Nothing
ghci> Map.insert "x" 7 values
fromList [("w",4),("x",7),("z",3)]
ghci> values						--immutability
fromList [("w",4),("z",3)]
ghci> Map.insert "x" 1 (Map.insert "y" 2 values)
fromList [("w",4),("x",1),("y",2),("z",3)]
ghci> values
fromList [("w",4),("z",3)]
withdraw :: String -> Int -> Map.Map String Int -> Map.Map String Int
withdraw account amount bank =
  case Map.lookup account bank of
    Nothing  -> bank                                   -- account not found, no change
    Just sum -> Map.insert account (sum-amount) bank   -- set new balance
    
ghci> bank = Map.fromList [("Bob",100),("Mike",50)]
ghci> bank
fromList [("Bob",100),("Mike",50)]
ghci> withdraw "Bob" 80 bank
fromList [("Bob",20),("Mike",50)]
ghci> bank
fromList [("Bob",100),("Mike",50)]
ghci> withdraw "Bozo" 1000 bank
fromList [("Bob",100),("Mike",50)]

Data.Array

import Data.Array
array :: Ix i => (i, i) -> [(i, e)] -> Array i e
-- Array lookup
(!) :: Ix i => Array i e -> i -> e

-- Array update
(//) :: Ix i => Array i e -> [(i, e)] -> Array i e
myArray = listArray (7,11) ["seven","eight","nine","ten","eleven"]

ghci> myArray
array (7,11) [(7,"seven"),(8,"eight"),(9,"nine"),(10,"ten"),(11,"eleven")]
ghci> :t myArray
myArray :: Array Integer String
ghci> myArray ! 8
"eight"
ghci> myArray // [(8,"ocho"),(9,"nueve")]
array (7,11) [(7,"seven"),(8,"ocho"),(9,"nueve"),(10,"ten"),(11,"eleven")]
ghci> myArray
array (7,11) [(7,"seven"),(8,"eight"),(9,"nine"),(10,"ten"),(11,"eleven")]

Folding over Maps & Arrays 

length (array (7,11) [(7,"seven"),(8,"eight"),(9,"nine"),(10,"ten"),(11,"ELEVEN")])
  ==> 5
foldr (+) 0 (Map.fromList [("banana",3),("egg",7)])
  ==> 10

4.7 Reading Docs

stack haddock --open
stack haddock --open <package>
profile
정나영
이전 포스트

✏️Chapter 1. 자료구조와 알고리즘

다음 포스트

🐞 JavaScript 문법

0개의 댓글