3

I recently found use for the following Haskell functions:

feed :: (a -> (a, b)) -> a -> Int -> (a, [b])
feed f input 0 = (input, [])
feed f input n
  | n < 0 = error "feed f input n: n < 0"
  | otherwise = (final, out:prev)
    where (next, out) = f input
      (final, prev) = feed f next $ pred n

nest :: (a -> a) -> a -> Int -> a
nest f x 0 = x
nest f x n
  | n < 0 = error "nest f x n: n < 0"
  | otherwise = f $ nest f x $ pred n

feed cycles a function through some input a, with the function returning a new input for the next call, as well as "emitting" an output, which is collected. nest works the same way, but doesn't let functions emit anything.

This looks awfully "Monadic" to me, and it seems to me like something from Control.Monad should already be doing this (I've caught myself trying to re-implement stuff like sequence, mapM, etc., out of necessity before, since I'm a beginner with Haskell and I don't quite know what's in the library and what's not.

Does something like the above (perhaps in a more general setting?) already exist? I've looked through the docs (at least the one's I'm familiar with), and can't find anything, though this seems like a common pattern. Example usage:

let pick10 rng = feed (swap . randomR (1, 10)) rng 10
  • Did I overlook something or shouldn't there be feed f next $ pred (n - 1) at the end of the feed function? – Giorgio Jan 12 '15 at 8:14
  • @Giorgio Isn't pred (n - 1) = n - 2? That would err on odd numbers. – VF1 Jan 12 '15 at 18:41
  • 1
    I think the main thing you're poking at here is unfold. That's the most general concept of "seed function repeated on it's own outputs" which is twisted into various more specific things than unfold, but most of those can be built from unfold - for instance by attaching a bind operation to the seed function or other various things - but unfold is the most general concept of this (I believe?) or Anamorphism in category theory – Jimmy Hoffa Jan 12 '15 at 19:57
  • @VF1: Sorry I misread your code: I read prev (the variable) insted of pred (the function). I thought you needed to decrement the variable but you actually already do. – Giorgio Jan 12 '15 at 22:04
  • 1
    Regarding your question, I had thought about using a state or a writer monad to accumulate the list of results, but I have not been able to come up with a proper solution yet so I do not know if they would fit. – Giorgio Jan 12 '15 at 22:15
7

Note: This answer might be a bit more basic than you are looking for. Maybe someone will find it useful.

feed is a bit like Data.List.unfoldr. It's not constrained to Ints. You could generalize yours over Enums if you wanted. iterate is similar, but produces an infinite list.

Main Data.List> unfoldr (\x -> if x > 9 then Nothing else Just (x, x + 1)) 0
[0,1,2,3,4,5,6,7,8,9] 
Main Data.List> feed (\x -> (x + 1, x)) 0 10
(10,[0,1,2,3,4,5,6,7,8,9])

nest is a bit like iterate because of infinite lists. Again, not constrained by the Int type.

*Main Data.List> iterate (+ 1.5) 2.7 !! 10
17.7
*Main Data.List> nest (+ 1.5) 2.7 10
17.7

As for Monadic, I'm not sure. [a] is one built-in Monad, and of course unfoldr f for whatever f is a nice a -> [a]. I do think you could define a Monad instance for your type (a, [b]) that left a trail and continued with the 'new' seed. There's probably an instance laying around that does that (Oop! You found it as I was writing this) - and, as always, these 'simple' things take just a few lines to write when you want them.

1

After some more digging it finally came to me. Indeed, there is such a generalization, and it was staring at me the whole time. The awfully monadic feeling I was getting was there because there really was a monad, simulated with tuples, lurking in the backgroud.

For those in suspense, it's replicateM along with Control.Monad.Random (for my example).

Note: I'll post a more detailed answer when I have time; just wanted to resolve the question to save viewers some effort.

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.