How do I code my Applicative stateful computation?

0
votes

Lets say I have a Traversable datum containing a handful of association pairs (Index, Fruit):

type Index = Int
data Fruit = Apple | Orange | Tomato

defaultFruit = Tomato

convertFruits :: (Traversable t) => t (Index, Fruit) -> Int -> [Fruit]
convertFruits input n = undefined

convertFruits is supposed to return a list of length n filled with Tomatos, except for all places where the input contained an association pair with a matching index — in which case the matching Fruit from input is placed at the matching index.

Examples of expected output:

convertFruits [] 4 = [Tomato, Tomato, Tomato, Tomato]
convertFruits [(2, Apple)] = [Tomato, Apple, Tomato, Tomato]
convertFruits [(1, Orange), (3, Orange), (4, Apple)] = \
    [Orange, Tomato, Orange, Apple]

How can I define such a function? Can I code a pure approach efficiently, avoiding O(n²)?

I see that there's traverse which takes Applicative actions, and Applicative looks a lot like Monad. But in contrast to good ol' Monad, I'm not really acquainted to Applicative, practically speaking. Any help?

2
haskell
just to make sure I understand - the output for convertFruits [(2,Apple),(1,Orange),(2,Orange)] 4 should be [Tomato,Orange,Orange,Tomato] ? – Random Dev
Could you please show some example input and output of what you want from this function, it is not very clear right now. – bheklilr
@CarstenKönig, that's left unspecified/not important; in my case there's a runtime guarantee that index-value pairs will have unique indices. So your behavior is fine (any is). – ulidtko
@bheklilr, yeah, sorry, my bad. I'll give example in a minute. – ulidtko
If you don't return a t any way, you don't need Traversable: Foldable should be enough. Or do you want t (Index, Fruit) -> Int -> t Fruit? Seeing your examples, both seem wrong, why don't you just use Map Index Fruit -> Int -> [Fruit]? – leftaroundabout

2 Answers

7
votes

First of all, you don't need Traversable in this scenario, since your result is a list. Foldable is good enough. Lets forget even that for a second. How would convertFruits look like if you would stick only to lists?

import qualified Data.Vector as V
import           Data.Vector ((//))

-- O(n + length input)
convertFruitsList :: [(Index, Fruit)] -> Int -> [Fruit]
convertFruitsList input n = V.toList $ V.replicate n Tomato // input'
  where input' = map (\(ix, f) -> (ix - 1, f)) input
        -- Vector is 0-indexed, so we need to adjust the indices

Now, how could one do the same for Foldable t (Index, Fruit) -> Int -> [Fruit]? That's also simple:

import Data.Foldable (toList, Foldable)

convertFruits :: Foldable t => t (Index, Fruit) -> Int -> [Fruit]
convertFruits input n = convertFruitsList (toList input) n

As you can see, it's not necessary to use traverse or Applicative in this scenario at all.

6
votes

This is a perfect use for the ST monad:

import Data.Array.ST
import Data.Array(elems)
import Data.Traversable

type Index = Int
data Fruit = Apple | Orange | Tomato
    deriving Show

defaultFruit = Tomato

convertFruits :: (Traversable t) => t (Index, Fruit) -> Int -> [Fruit]
convertFruits input n = elems $ runSTArray $ do 
    a <- newArray (1,n) defaultFruit
    _ <- for input $ uncurry (writeArray a)
    return a

ST lets you use mutability to get your efficient O(n) algorithm within a pure computation.