본문 바로가기

Haskell

Applicative에 대해 함수를 사상할 수 있는 데이터 구조를 functor라 한다. 흔히 fmap 함수를 적용할 수 있는 타입을 말하는데, 기본적인 functor로는 리스트, Maybe 등이 있다. 이 때의 fmap의 타입은 a -> b 로 단인자 함수가 흔히 상정된다. 예를 들어 fmap (+1) [1,2,3] 이나 fmap (*2) (Just 3) 등의 식은 단인자 함수인 (+1), (*2) 를 functor에 맵핑하여 새로운 값을 만들어낸다. 만약 사상하는 함수가 단인자 함수가 아닌 경우라면 어떨까? fmap (*) (Just 3)이라는 표현식은 어떤 결과를 내놓을까? (아니면 그냥 펑하고 터지게 될 것인가?)하스켈의 함수는 기본적으로 항상 커링된다. 즉 어떤 함수의 타입이 (a, b) -> c 가 아닌 a -> b ->.. 더보기
기본적인 입출력과 모나드 대부분의 프로그래밍 언어는 입출력에 관련한 '함수'를 제공한다. 그리고 이런 함수들은 기본 중의 기본으로 취급되면서 '있는 그대로 쓰면 되는 것'으로 취급된다. 예를 들어 파이썬의 경우에 입출력함수는 input(), print()가 있다. 특히 input()과 같이 표준 입력을 받아오는 함수의 경우, 함수를 평가한 결과가 키보드등으로 입력된 문자열 값이 된다. 물론 하스켈의 경우에도 입출력 함수가 있다.(그것도 여러개) 하지만 다른 언어에서 가장 기본중의 기본이 되는 입출력이 하스켈에서는 그리 간단한 일이 아니다. 그것은 하스켈이 순수 함수형 언어라는 디자인 특성을 가지고 있기 때문인데, 따라서 입출력 자체는 어렵지 않은 일이나, 그것을 다루는 방법이 제법 까다롭다. 입출력을 담당하는 기본 함수 하스켈은.. 더보기
커스텀 타입을 정의하는 법 data 키워드는 새로운 데이터 타입을 정의할 때 사용된다. 새로운 타입을 정의하는 방법은 크게 두 가지가 있다. 열거형으로 정의하기 조합형으로 정의하기 열거형은 대수적 타입을 정의할 때 흔히 사용할 수 있다. data 타입명을 좌변으로 하고 등호의 우변에는 타입의 개별 값을 |로 구분지어 넣는다. 이 때 열거형의 개별 값은 인자를 받지 않는 constructor로 간주되므로 대문자로 작성한다. 예를 들어 Bool 타입은 다음과 같이 정의될 수 있다. data Bool = True | False 여기서 Bool 자체는 데이터 타입의 이름이며, True, False는 각 열거케이스에 해당하는데 이 각각은 하나의 값을 생성하기 위해 호출되는 constructor이다. 다른 데이터 타입 정의 방식으로는 조합형.. 더보기
지정된 횟수만큼 처리를 반복하기 온라인 저지 사이트의 문제들은 주어진 task를 수행하는 코드를 작성하게 한 다음, 지정된 포맷의 입력을 처리하게 한다. 이 때 입력은 전통적으로 다음과 같은 형식을 취하는 경우가 많다. 최초 입력되는 값은 정수값으로 몇 번 반복할 것인지를 결정한다. 이후 매 행마다 데이터를 입력하고, 이것을 1에서 입력한 값 만큼 제공한다. 일반적인 프로그래밍 언어에서는 이 과정이 별다른 테크닉을 요구하지 않는다. 기본적인 입력 방법과 반복문을 사용해서 처리하게 된다. 예를 들어 파이썬이라면 다음과 같이 코딩할 수 있겠다. n = int(input()) for _ in range(n): x = input() solve(x) 그런데 하스켈에서는 이를 어떻게 처리할 수 있을까? 간단한 문제가 하나 있다고 하자. 정수 하나.. 더보기
최대 공약수를 찾는법 조금 어려운 초급 연습문제. 어떤 임의의 정수 N을 소인수 분해한 결과가 다음과 같다고 하자.$$ p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times p_2^{a_4} ... $$이를 [p1, a1, p2, a2, p3, a3 ... ]의 리스트로 표현하기로 약속한다. 리스트의 개수 N을 입력받고 이후 N 줄에 대해서 각각 공백으로 띄워진 숫자리스트를 입력받는다. 리스트는 인수와 지수의 짝이어야 하므로 짝수개의 인자가 들어오는 것을 보장한다.자 이렇게 구성된 N 개의 정수들의 최대 공약수를 구해서 입력과 동일한 형태의 리스트로 출력하는 프로그램을 작성해보자. 접근 가장 손쉬운 방법은 Integer 타입으로 만들어서 gcd 함수를 적용하는 것이다. 이는 만들어지는 각.. 더보기
원소 필터링 문제 연습문제 - 이번에는 약간 쉽지 않다. N개의 정수로 이루어진 리스트 A를 받는다. 그리고 정수 K를 받는다. 리스트 A에서 K번 이상 등장한 정수들을 필터링하여, 최초에 등장했던 순서대로 출력하는 것이다. 예를 들어 A = [4, 5, 2, 5, 4, 3, 1, 3, 4] 이고, K=2라면 이 중에서 두 번 이상 등장한 원소는 순서대로 4, 5, 3 이므로 출력은 4 5 3 이다. 만약 K번 이상 등장한 원소가 없다면 -1을 출력해야 한다. 출처 : https://www.hackerrank.com/challenges/filter-elements/problem입력 첫줄에서는 시행횟수를 받는다 각 시행의 첫입력은 리스트의 길이와 K 값을 공백으로 구분하여 받음 각 시행의 둘째 입력은 리스트의 내용 접근 원.. 더보기
고유문자로 축약하기 이번에는 이전에 풀어본 문자열 압축과 비슷하다. 한 번 나온 순서대로 문자열을 한 번만 표시하는 것이다. 출처 : https://www.hackerrank.com/challenges/string-reductions/problem 사실 별로 어렵지 않다. import Data.List test :: String -> String test x = helper "" x where helper acc xs = case xs of [] -> reverse acc (y:ys) -> if y `elem` acc then helper acc ys else helper (y:acc) ys 붙여나가는 순서를 역순으로하여 리스트 처리에 부담을 줄여주는 것으로 성능은 제법쓸만하다. elem은 리스트에 특정 원소가 있는지를 알.. 더보기
몇 가지 간단한 연습문제 기타 몇 가지 하스켈 초급 문제들을 해결해보고, 입출력을 처리하는 과정을 살펴보자. 리스트를 뒤집기 일련의 리스트를 입력된 순서를 거꾸로하여 출력한다. 단, reverse 함수를 쓰지 말 것. (https://www.hackerrank.com/challenges/fp-reverse-a-list/problem) 이 문제는 reverse 함수를 구현해보라는 의미이다. 예를 들어 1 2 3 의 리스트가 있다고 할 때, 이를 (2 3을 뒤집은 결과) + [1] 로 만드는 처리를 재귀적으로 수행하면 역순의 리스트를 만들 수 있다. 따라서 다음과 같은 함수를 정의할 수 있다. rev :: [a] -> [a] rev [] = [] rev (x:xs) = (rev xs) ++ [x] 실제로 이 구현은 '매우 정직한' .. 더보기

티스토리툴바