State exercise

134 views
Skip to first unread message

Ramakrishnan Muthukrishnan

unread,
Jan 1, 2015, 2:10:16 PM1/1/15
to haskell-...@googlegroups.com
Hi,

I am trying to do the State exercise (State.hs). It looks like there
is something I am clearly missing here. I implemented firstRepeat by
following the types.

firstRepeat :: Ord a => List a -> Optional a
firstRepeat xs = eval (findM (\x -> State (\s -> (S.member x s,
S.insert x s))) xs)
S.empty

By the same method, I implemented distinct, but it is clearly not
working as intended.

distinct :: Ord a => List a -> List a
distinct xs = eval (filtering (\x -> State (\s -> (S.notMember x s,
S.insert x s))) xs)
S.empty

My `distinct' is passing in all the elements.
(I haven't looked at simplifying the above expressions. I want to get
it produce correct values first and then simplify.)

My implementation of `filtering' is this:

filtering :: Applicative f => (a -> f Bool) -> List a -> f (List a)
filtering f xs = lift2 removeFalse (tagList f xs) (pure xs)

tagList :: Applicative f => (a -> f Bool) -> List a -> f (List Bool)
tagList f xs = sequence (foldRight (\x acc -> (f x) :. acc) Nil xs)

removeFalse :: List Bool -> List a -> List a
removeFalse Nil _ = Nil
removeFalse _ Nil = Nil
removeFalse (True :. bs) (x :. xs) = x :. removeFalse bs xs
removeFalse (False :. bs) (_ :. xs) = removeFalse bs xs

Any hint to debug the problem will be appreciated.

Thanks for the wonderful exercises!
--
Ramakrishnan
https://rkrishnan.org/

Ramakrishnan Muthukrishnan

unread,
Jan 1, 2015, 9:47:05 PM1/1/15
to haskell-exercises
Never mind. A good night's sleep revealed a very subtle bug in my
instance implementation of `Apply', which showed up as a bug in
`distinct'. :)

I am having a lot of fun with the exercises. Thanks again.

Ramakrishnan

Tony Morris

unread,
Jan 1, 2015, 9:51:34 PM1/1/15
to haskell-...@googlegroups.com
Sleep always works. Where was your bug?
Reply all
Reply to author
Forward
0 new messages