리스트의 각 원소를 복제하기

원문 : https://www.hackerrank.com/challenges/fp-list-replication/problem

이번 문제는 리스트 복제와 관련된 문제이다. replicate를 이용해서 특정한 타입의 값을 N회 반복하는 리스트로 만드는 것을 응용한다.

문제에서는 아래와 같은 스텁이 주어진다.


main :: IO ()
main = getContents >>=
       mapM_ print . (\(n:arr) -> f n arr) . map read . words
       
f n arr = -- implement this function

접근

일단 문제에 집중하자. 문제는 일련의 숫자가 (한 줄에 하나씩) 주어졌을 때, 맨 첫 숫자만큼 각 숫자를 반복한 리스트를 만드는 것이다. 편의상 한 칸에 하나의 숫자를 썼을 때 3 1 2 3 --> 1,1,1,2,2,2,3,3,3 과 같은 식으로 리스트를 생성한다.

입력된 데이터를 가공하여 [Int] 타입으로 만들었다 할 때 이 때의 head 부분은 반복횟수이며, 나머지 tail 부분이 적용될 리스트가 된다. 그렇다면 이건 replicate n을 flatMap에 적용한 것이랑 똑같은 상황이된다.

그런데 애석하게도(?) haskell에는 flatMap이 없다. 놀랍지만 진짜임;; 대신에 concatMap이라는 함수를 제공한다. 이걸 그대로 쓰면 된다.


f n arr = concatMap (replicate n) arr

문제에 등장한 무서워보이는 main 함수를 분석해보자.

getContents라는 함수를 썼다. 이 함수를 일련의 연속된 라인입력을 처리하여 하나의 문자열로 합쳐주는 함수이다.

이 결과를 1) 분해하고 2) 정수 리스트로 변환하고 3) f 함수에 적용하고 4) 출력한다는 순서는 다음의 문구로 처리할 수 있다.

먼저 문자열을 공백 기준으로 분해하는 것을 words 함수를 쓴다. 이 결과는 [String]이 되는데, 여기의 각 원소를 정수로 읽어들이려면 read 함수를 맵핑한다. 따라서 다음 함수가 여기까지의 처리를 맡게 된다.


map read . words

이번에는 정수 리스트를 받아서 f 함수를 적용하는 함수는 다음과 같이 익명 함수를 이용해서 작성할 수 있을 것이다.


map (\(n:arr) -> f n arr) . map read . words

여기에 print 를 추가하면 맵핑이 적용된 리스트의 각 원소를 출력할 수 있다.


map print . (\(n:arr) -> f n arr) . map read . words

자 이함수는 String -> [IO ()]로 만드는 함수이다. 그리고 getContents는 IO String이다. 우리가 원하는 최종 함수는 IO String -> (String -> IO ()) -> IO ()를 만드는 함수여야 한다.

mapM 이 이와 비슷한 역할을 한다.


mapM :: Monad m => (a -> m b) -> [a] -> m [b]

우리는 마지막 단계에서 맵핑된 결과가 필요 없기 때문에 mapM 대신에 mapM_을 사용할 것이다.


mapM_ :: Monad m => (a -> m b) -> [a] -> m ()

위에서 정리한 결과에 대해서 mapM_을 사용해보자.


mapM_ . print . map(\(n:arr) -> f n arr) . map read . words

이 함수는 String -> IO () 인 함수이다. 그리고 최초의 입력은 IO String이다. 따라서 >>= 연산자를 이용해서 이 함수에 입력값을 주입할 수 있다. >>=를 풀어쓴 형태는 fmap f xs가 된다.


(>>=) :: Moand m => m a -> (a -> m b) -> m b

최종 main 함수의 형태는 따라서,


main = getContents >>= mapM_ . print . map (\(n:arr) -> f n arr) . map read . words

가 된다.