Haskell function to error-diffuse a floating value to a list of integers

Question

I needed to write a function which would 'error diffuse' floating values to integers:

errorDiffuse :: Double -> Int -> Double -> [Int]

errorDiffuse _ 0   _   = []

errorDiffuse v num err = tv : errorDiffuse v (num - 1) (err + v - fromIntegral tv)
  where tv = truncate (v + err)

So that, for example:

errorDiffuse 1.4 10 0 => [1,1,2,1,1,2,1,2,1,1]

(i.e., the function produces a list of num integers, each of which is the ceiling or floor of v, starting with a given error value (zero in this case)).

Is there a better way to write this sort of for loop? What's the higher-order function I ought to be thinking in terms of?

Nicolas Wu · Accepted Answer · 2011-11-02 15:45:07Z

First I'd get rid of the dependency on num, since that's just a counter, and you can use take num on an infinite list of errorDiffuses:

errorDiffuses :: Double -> Double -> [Int]
errorDiffuses v err = tv : errorDiffuses v (err + v - fromIntegral tv)
 where
  tv = truncate (v + err)

So we have:

errorDiffuse' :: Double -> Int -> Double -> [Int]
errorDiffuse' v num err = take num $ errorDiffuses v err

Then I'd think about generating the list of errorDiffuses differently. Since we're trying to generate a list, that makes me think of unfolds, which you can find in Data.List:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

The unfold takes a function that, given a seed, produces the next value in the outputted list, along with a new seed. The function starts with an intitial seed, and keeps using those seeds, adding to the list until the function returns Nothing.

The function we're looking for is the following:

nextErrorDiffuse :: Double -> Double -> Maybe (Int, Double)
nextErrorDiffuse v err = Just (tv, err + v - fromIntegral tv)
 where
  tv = truncate (v + err)

Our list is infinite, so we always return a Just value. The value that is output at each stage is tv, and the next "seed" is given by err + v - fromIntegral tv.

Putting things together we have:

errorDiffuse'' :: Double -> Int -> Double -> [Int]
errorDiffuse'' v num err = take num $ unfoldr (nextErrorDiffuse v) err

Fantastic, thankyou! I don't think unfoldr is in my mental toolkit yet but it was exactly the sort of thing I was thinking of. — stusmith
– stusmith, Commented Nov 2, 2011 at 16:34
unfoldr is a great tool to add to your toolkit. Whenever you need to produce a list from some seed value(s), unfoldr should come to mind. — Dan Burton
– Dan Burton, Commented Nov 26, 2011 at 20:03

Stack Exchange Network

Haskell function to error-diffuse a floating value to a list of integers

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Haskell function to error-diffuse a floating value to a list of integers

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions