Cleaning up mutable array code

Question

I'm trying to solve the MINFREE problem in "Pearls of Functional Algorithm Design" using mutable arrays. The problem is as follows: given a list of n natural numbers, find the smallest natural number that does not appear in the list. I'm pretty sure that the following is a solution:

minFree2 :: [Int] -> Int
minFree2 ns =  (fromMaybe 0 $ elemIndex True seen)
  where
    bound = (1, length ns)
    seen = elems $ runSTArray $ do
      arr <- newSTArray bound False
      mapM_ (\n -> writeArray arr n False) ns
      return arr

But the do block looks awfully imperative to me, and I'd like to simplify it to a more functional style in order to get a better grasp on monads.

I can get as far as the following (rewriting only the where clause):

 bound = (1, length ns)
 setTrues arr = mapM_ (flip (writeArray arr) False) ns
 seen = elems $ runSTArray $ newSTArray bound False >>= setTrues

But that doesn't work, because it returns () rather than STArray s i e. I'd like to write something like:

    setTrues arr = mapM_ (flip (writeArray arr) False) ns >> arr

the same way I might write fn arr => map ....; arr in SML, but that doesn't work here because arr is an STArray s i e rather than a ST s (STarray s i e). I'd expect to be able to fix that by wrapping arr back up in an ST, but my attempt with:

    setTrues arr = mapM_ (flip (writeArray arr) False) ns >> arr
    seen = elems $ runSTArray $ newSTArray bound False >>= return . setTrues

Yields the error:

No instance for (MArray (STArray s) Bool (STArray s Int))
  arising from a use of `setTrues'

which I don't entirely understand.

Is there a nice way to write this code, minimizing the use of do?

Note that this is the example in chapter 1 of Richard Bird's Pearls of Functional Algorithm Design, and his results show that a divide-and-conquer approach using pure structures beats an accumArray based approach. — Carl
– Carl, Commented Apr 15, 2015 at 14:53

chi · Accepted Answer · 2015-04-15 11:01:18Z

2

This should work:

setTrues arr = mapM_ (flip (writeArray arr) False) ns >> return arr
seen = elems $ runSTArray $ newSTArray bound False >>= setTrues

The trick is letting setTrues return the array instead of (), as you already attempted.

edited Apr 15, 2015 at 11:01

answered Apr 15, 2015 at 9:08

chi

117k4 gold badges143 silver badges230 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Patrick Collins Over a year ago

Whoops. I feel a bit silly having overlooked that. The Control.Applicative solution is much cleaner, though -- thanks for pointing that out. I'd be extra happy if setTrues could be rewritten to be point-free, but I suspect that can't be done sanely.

Patrick Collins Over a year ago

Actually, I don't think <* does the trick -- I get Couldn't match expected type ST s b0' with actual type a0 Int Bool -> m0 ()' --- setTrues isn't passed the STArray as an argument.

Martin Huschenbett · Accepted Answer · 2015-04-15 10:14:25Z

1

To my understanding, one of the main purposes of the ST monad is to provide a loophole to imperative programming in purely functional code. So I guess, there is no nice solution using the ST monad which doesn't look too imperative. However, to get rid of the imperative style you could use the function

accumArray :: Ix i => (e -> a -> e) -> e -> (i, i) -> [(i, a)] -> Array i e

from Data.Array. In fact, the actual implementation of this function looks somewhat similar to your code.

Altogether, a more functional solution could look as follows:

minFree2 :: [Int] -> Int
minFree2 ns = fromMaybe 0 $ elemIndex False $ elems seen
  where
    bound = (1, length ns)
    seen :: Array Int Bool
    seen = accumArray (||) False bound $ map (,True) ns

PS: True and False seemed to be distributed slightly wrong. I silently fixed this.

answered Apr 15, 2015 at 10:14

Martin Huschenbett

5583 silver badges9 bronze badges

1 Comment

Patrick Collins Over a year ago

This is a better solution, but I'm interested in one using mutable arrays for my purpose here -- I have a reference solution with an accumArray that I'm comparing against. Perhaps, though, the ugliness of ST is inevitable.

Collectives™ on Stack Overflow

Cleaning up mutable array code

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related