3
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ – stusmith Nov 2 '11 at 16:34
  • \$\begingroup\$ Glad I could help :-) \$\endgroup\$ – Nicolas Wu Nov 2 '11 at 16:37
  • \$\begingroup\$ 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. \$\endgroup\$ – Dan Burton Nov 26 '11 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.