Home » Haskell

Haskell

예제로 이해해보는 모나드 – 파서구현하기

Applicative Functor가 Functor를 확장하는 것처럼, 모나드도 Applicative의 차원을 확장한 것이라 할 수 있습니다. 하지만 그것은 단순한 기술적인 설명일 뿐이며 모나드에서는 그 모나드가 가지는 계산적 맥락이 어떤 특성을 갖는지를 이해하는 것이 중요합니다. (그리고 이것은 매우 추상적이라 쉽지 않습니다.)

이런 경우 구체적인 예를 들어가며 살펴보는 것이 좋은데, 모나드의 경우 흔히 파서(Parser)를 예로 듭니다. 파서란 어떤 해석기 같은것을 만들 때, 가장 앞단에 위치하는 부분으로 (주로) 문자열로 이루어진 데이터를 정해진 문법적 규칙(리터럴)에 맞게 토큰으로 분리하고, 각 토큰이 갖는 논리적 관계에 맞게 트리를 만들어내는 논리장치입니다. 어떠한 데이터, 특히 코드를 해석하는 모든 프로그램은 파서를 가지고 있습니다. 모든 언어의 컴파일러나 인터프리터는 기본적으로 해석기 이므로 파서가 필요합니다. 웹브라우저는 HTML 코드를 읽고 그 문법적 구조를 이해해야 하기 때문에 HTML 코드를 잘라내는 파서를 가지고 있습니다.

실질적으로 유용하고 의미있는 작업을 하는 파서를 만드는 것은 사실 매우 어렵고 복잡한 일입니다. 여기서는 단지 파서를 핑계로 모나드를 이해하는데 도움을 주려하기 때문에 아주 단순하면서도 쓸모없는 간단한 파서의 타입을 정의해보겠습니다.

더 보기 »예제로 이해해보는 모나드 – 파서구현하기

하스켈에서 메모이제이션 구현하기

하스켈의 메모이제이션 하스켈의 함수는 순수함수이고, 이는 입력이 같다면 항상 같은 결과가 리턴되는 것을 보장한다. 이는 어떤 임의의 함수 f와 그 인자 x가 있을 때 최초 f(x)가 계산되고 나면 그 이후에 f(x)가 필요한 경우에 불필요한 반복 계산이 필요하지 않은 것 처럼 들린다. (왜냐면 f(x)는 이미 이전에 계산되어 값으로 축약되었고, 그 사이에 어떤 일이 있었든지 간에 같은 인자에 대해서는 하스켈의 함수는 같은 결과를 내놓을 것이기 때문이다.) 하지만 이것은 다른 문제이다. 이는 하스켈이 기본적으로 모든 함수 적용 연산에 대해 그 결과를 캐싱한다는 이야기인데,… 더 보기 »하스켈에서 메모이제이션 구현하기

(연습문제) 리사의 워크북 문제

Lisa의 워크북 문제 https://www.hackerrank.com/challenges/bear-and-workbook n개의 챕터가 있는 워크북이 있고, 이 워크북의 매 페이지는 k 개 문제를 담을 수 있다. 이후에 n 개의 정수를 받는데 이는 각 챕터의 문제 수이다. 각 챕터의 문제는 1번 부터 시작하며, 새로운 챕터는 새 페이지에서 시작한다. 이 때, 문제번호와 페이지번호(1번부터 시작)가 같은 문제를 특별한 문제라고 할 때, 주어진 데이터 내에서 특별한 문제의 개수를 구하라는 내용이다. 풀이 이 문제는 하스켈에서 의외로 쉽게 풀린다. 다음과 같은 순서로 풀어보자. 숫자 x 를 받았을 때, [[1,2,3], [4,5,6], [7]] 과 같이… 더 보기 »(연습문제) 리사의 워크북 문제

(연습문제) 대소문자변환

연습문제 : 대소문자 변환하기 입력받은 문자열의 대소문자를 반전하여 출력하는 프로그램을 작성하시오. 입력받은 각 글자의 문자 코드가 ‘a’ … ‘z’ 사이에 있으면 소문자, ‘A’~’Z’ 사이에 있으면 대문자이다. 그리고 그 변환은 해당 코드값에 a – A를 더하거나 빼주면 된다. 먼저 대소문자의 범위를 찾아보자. print("azAZ".utf8.map(Int.init)) //=> [97, 122, 65, 90] 즉 문자 코드가 97~122 구간에 있으면 소문자, 65~90 구간에 있으면 대문자이다. 소문자->대문자 변환은 32를 빼고, 반대의 변환은 32를 더한다. 문자 코드 값으로 다시 문자를 만드는 방법은 다음과 같다. 문자열은 [Character] 타입으로 만들 수… 더 보기 »(연습문제) 대소문자변환

하스켈에서 조합 구현하기

하스켈 연습문제 주어진 리스트에서 중복되지 않은 모든 부분집합을 만들어라. 주어진 리스트에서 n 개를 비복원추출한 조합은 다음과 같이 만든다. combinations :: Int -> [a] -> [[a]] combinations 0 _ = [[]] combinations n xs = [ xs !! i : x | i <- [0..(length xs)-1], x <- combinations (n-1) (drop (i+1) xs)] > combinations 2 [1..4] [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] n 개짜리 원소의 리스트의 모든 부분집합은 따라서 다음과 같이 구한다. combinationAll xs = concatMap (\n -> combinations n xs) [0..length xs] tails 함수를… 더 보기 »하스켈에서 조합 구현하기

(Haskell) Applicative Functor

Applicative Functor

Applicative Functor는 하스켈의 Control.Applicative 모듈에서 정의하고 있다.
하스켈의 함수는 알다시피 모두 자동으로 커리된다. a -> b -> c 타입의 함수 f가 있다고 할 때, 인자 하나를 전달한 f x의 타입은 b -> c인 함수가 된다. 함수 역시 Functor의 일종이며, 따라서 함수에 함수를 맵핑하는 것 (이는 함수 합성과 동일하다)도 가능했다. 다만 이 때의 사상되는 함수들은 모두 단인자 함수임에 주목하자.

f x = x + 1
g x = x * 2
fmap g f = g . f = (\x -> g (f x))

그런데 *처럼 인자 두 개를 받는 함수를 다른 함수에 적용하면 어떻게 될까? 예를 들어 (*) 함수를 Just 3 같은 곳에 맵핑하면 무슨 일이 벌어질까? 더 보기 »(Haskell) Applicative Functor

how lazy evaluation works in haskell

Lazy evaluation이 동작하는 방식 게으른 평가(lazy evaluation)는 하스켈 프로그램이 실행될 때 광범위하게 사용된다. 게으른 평가의 적용은 코드를 보다 단순하게 만들어줄 수 있지만, 초보자에게는 종종 메모리 사용과 관련된 함정이 되기도 한다. 예를 들어 foldl (+) 0 [1..10^8] 이라는 간단한 표현식은 계산에 있어 수기가바이트의 메모리를 요구한다. 게으른 평가는 일종의 트레이드 오프이다. 이는 코드를 단순하게 만들어주지만 그것이 튺정한 프로그램에서 실제로 어떻게 평가하는지 완전히 이해할 수는 없게 된다. (케바케라서…) 그래프 축약 하스켈 프로그램은 표현식을 평가하는 것으로 실행된다. 다음 함수를 예로 들어보자. square x =… 더 보기 »how lazy evaluation works in haskell

오일러 프로젝트 20

이번 문제는 100!의 모든 자리수 숫자들의 합을 구하는 것이다.   n! 이라는 표기법은 n × (n − 1) × … × 3 × 2 × 1을 뜻합니다. 예를 들자면 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800 이 되는데, 여기서 10!의 각 자리수를 더해 보면 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 입니다.     100! 의 자리수를 모두 더하면 얼마입니까?””” (http://euler.synap.co.kr/prob_detail.php?id=20) 접근 팩토리얼 함수는… 더 보기 »오일러 프로젝트 20