How to use Control.Monad.Cont in a recursive function?

Question

I was providing an answer to this question and an idea came to me to use Cont monad. I don't know Haskell enough to explain why this program doesn't work

import Control.Monad.Cont

fib1 n = runCont (slow n) id
  where
    slow 0 = return 0
    slow 1 = return 1
    slow n = do
      a <- slow (n - 1)
      b <- slow (n - 2)
      return a + b

main = do
  putStrLn $ show $ fib1 10

Error -

main.hs:10:18: error:
    • Occurs check: cannot construct the infinite type: a2 ~ m a2
    • In the second argument of ‘(+)’, namely ‘b’
      In a stmt of a 'do' block: return a + b
      In the expression:
        do a <- slow (n - 1)
           b <- slow (n - 2)
           return a + b
    • Relevant bindings include
        b :: a2 (bound at main.hs:9:7)
        a :: a2 (bound at main.hs:8:7)
        slow :: a1 -> m a2 (bound at main.hs:5:5)
   |
10 |       return a + b
   |

But this doesn't make sense to me. Why do I have a2 and m a2? I'm expecting a and b to be of the same type.

It's bugging me because the same program works just fine in JavaScript. Maybe the Haskell one needs a type hint?

const runCont = m => k =>
  m (k)

const _return = x =>
  k => k (x)
  
const slow = n =>
  n < 2
    ? _return (n)
    : slow (n - 1) (a =>
      slow (n - 2) (b =>
      _return (a + b)))
      
const fib = n =>
  runCont (slow(n)) (console.log)
  
fib (10) // 55

`return a + b` is parsed as `(return a) + b`. Try `return (a + b)` or `return $ a + b` instead. — Joseph Sible-Reinstate Monica, Feb 24 '19 at 05:43
I *highly* recommend putting type signatures for (at least) all top-level functions and bindings. It often makes the type error messages *significantly* easier to understand. Here I would recommend a type signature for the function in the `where` block as well. It also makes the code easier (and faster) to read. — David Young, Feb 24 '19 at 08:51
your `slow` here is actually [essentially applicative](https://stackoverflow.com/search?q=user%3A849891+essentially+monadic+applicative), not [monadic](https://stackoverflow.com/a/39647091/849891): `slow n | n < 2 = pure n ; slow n = [(a+b) | a <- slow (n-1), b <- slow (n-2)] = liftA2 (+) (slow $ n-1) (slow $ n-2)` (using Monad Comprehensions), since no sub-computation depends on / uses the results of no previous sub-computation. so the monad actually does nothing -- it's all just `return`s inside the `do`. for instance `runState (slow 10) 42` returns `(55,42)` so the state isn't used at all. — Will Ness, Jan 15 '22 at 08:04

score 6 · Accepted Answer · answered Feb 24 '19 at 05:42

6

return a + b parses as (return a) + b, whereas you wanted return (a + b). Remember that function application binds tighter than any infix operator.

(It's also common to write return $ a + b, which amounts to the same thing)

answered Feb 24 '19 at 05:42

Ben Millwood

6,754
24
45

1

why are people upvoting my answer it is boring – Ben Millwood Feb 24 '19 at 08:36
Why did you post the answer in the first place? – chepner Feb 24 '19 at 14:33
1

If a question has a trivial solution that can be answered fully in a comment, I just vote to close as "can no longer be reproduced". – chepner Feb 24 '19 at 14:35
1

I originally deleted the question, but then saw people already started up-voting this answer. If this answer was useful to others, I didn't want to take away the potential of future readers benefiting as well, so I undeleted it. My apologies if the question was too basic. – Mulan Feb 24 '19 at 19:43

How to use Control.Monad.Cont in a recursive function?

1 Answers1

Linked