Geek Answers Handbook

Data.Vector, display with battery

I would like to make a battery card on Data.Vector.

I want to write an inc function:

inc :: Vector.Vector Bool -> Vector.Vector Bool

which "adds one" to the vector, for example:

inc <False, False, False> = <False, False, True>
inc <False, False, True> = <False, True, False>
inc <True, True, True> = <False, False, False>

If something like Data.List mapAccumR, let's say with type:

mapAccumR :: (acc -> x -> (acc, y)) -> acc -> Vector x -> (acc, Vector y)

this can be done with

inc = snd . Vector.mapAccumR inc' True
  where
    inc' x y = (x && y, (x || y) && (not (x && y)))

but I cannot figure out how to do this with what is in Data.Vector.Unboxed. Is it possible?

+4
source share
1 answer

The simplest solution would be to reverse your circuit and have the least significant bits on the front of the vector, for example:

inc <False, False, False> == <True, False, False>

, mapM unfoldr inc , , vector . mapM inc :

import Control.Monad.State
import qualified Data.Vector.Unboxed as V

inc :: V.Vector Bool -> V.Vector Bool
inc v = evalState (V.mapM go v) True where
  go acc = state $ \x -> (x /= acc, x && acc)

, . , .

, mapAccumR. ST , , . ST ; , , . mapAccumR .

-- we need this so we can annotate objects in the ST monad with
-- the right parameters
{-# LANGUAGE ScopedTypeVariables #-}

import Control.Monad.ST.Strict
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as MV

-- note that I explicitly introduce the type variables
-- with forall. This - in conjunction with ScopedTypeVariables - 
-- lets us refer to the type variables in the function body.
mapAccumR ::
  forall x y acc.
  (V.Unbox x, V.Unbox y) =>
  (acc -> x -> (acc, y)) -> acc -> V.Vector x -> (acc, V.Vector y)
mapAccumR f acc v = runST $ do
  let len = V.length v

  -- Allocate a mutable unboxed vector of v size.
  -- We need to annotate the "s" parameter here, so we can
  -- refer to it in the type of "go".
  (mv :: MV.STVector s y) <- MV.unsafeNew len

  -- iterate through the new vector in reverse order,
  -- updating the elements according to mapAccumR logic.
  let go :: Int -> acc -> ST s acc
      go i acc | i < 0 = return acc
      go i acc = do
        -- y comes from the old vector
        -- we can access it via the immutable API
        let (acc' , y) = f acc (V.unsafeIndex v i)
        -- but we must do mutable writes on the new vector
        MV.unsafeWrite mv i y
        go (i - 1) acc'

  acc' <- go (len - 1) acc

  -- "unsafeFreeze" converts the mutable vector to
  -- an immutable one in-place.
  v'   <- V.unsafeFreeze mv
  return (acc', v')
+2

More articles:


All Articles