[Haskell] Maybe 와 Exception
글쓴이: esrevinu / 작성시간: 일, 2015/04/05 - 8:10오후
'Purely Functional Data Structures'라는 책을 읽고 있습니다.
책에 코드는 Standard ML을 쓰는데 해스켈 코드도 부록에 있네요. 연습문제 중에
UnbalancedSet의 insert, member 함수를 구현할 때 최악의 경우 비교를 트리의 깊이의 두 배 만큼 해야 하는데
이를 깊이+1만 하도록 하라는 연습문제가 있습니다. 그리고 insert 함수는 이미 Set에 있는 값을 넣는 경우 원래의 Set과
변화가 없으니 Exception을 발생시켜서 새로운 트리를 만들지 말고 기존의 트리를 돌려 주라는 요구가 있습니다.
해스켈은 Pure 함수에서 Exception을 발생시킬 수 없는 것 같고 그래서 Maybe를 사용했습니다.
다른 언어에서 Exception이 어떻게 구현되는지 모르겠지만 Maybe는 재귀 함수를 호출해서 결과를 받을 때마다
Nothing이냐, Just냐를 패턴 매칭해야 하는데 Exception처럼 빠르게 Catch하는 방법이 없을까요?
제 코드입니다. 주석처리한 것은 원래 코드입니다.
{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}
module UnbalancedSet (UnbalancedSet) where
import Set
import Data.Maybe (fromMaybe)
data UnbalancedSet a = E | T (UnbalancedSet a) a (UnbalancedSet a)
deriving Show
instance Ord a => Set UnbalancedSet a where
empty = E
-- member x E = False
-- member x (T a y b) =
-- if x < y then member x a
-- else if x > y then member x b
-- else True
member x s = remember s Nothing
where
remember E Nothing = False
remember E (Just v) = x == v
remember (T a y b) c = if x > y then remember b c
else remember a (Just y)
-- insert x E = T E x E
-- insert x s@(T a y b) =
-- if x < y then T (insert x a) y b
-- else if x > y then T a y (insert x b)
-- else s
insert x s = fromMaybe s $ insert' s Nothing
where
insert' E Nothing = Just (T E x E)
insert' E (Just v) = if x == v then Nothing
else Just (T E x E)
insert' (T a y b) c =
if x > y then
insert' b c >>= \k -> return (T a y k)
else
insert' a (Just y) >>= \k -> return (T k y b)Forums:
Continuation Passing Style
어렵네요.
continuation passing style로 해 보려고 하는데 잘 모르겠네요.
일단 간단하게 짰습니다.
insert x s = runCPS s id where runCPS t@(T a y b) = \k -> k $ if x < y then runCPS a $ \kk -> T kk y b else if x > y then runCPS b $ \kk -> T a y kk else t runCPS E = \k -> k $ T E x E한가지 조건을 만족시키는 코드
insert x s = runCPS s Nothing id where runCPS (T a y b) m = \k -> k $ if x > y then runCPS b m $ \kk -> T a y kk else runCPS a (Just y) $ \kk -> T kk y b runCPS E m = \k -> k $ case m of Nothing -> T E x E Just v -> if x == v then E else T E x E댓글 달기