maybeLoeb

[spitis]

Hi @quchen. I am fairly new to Haskell, and stumbled upon your loeb article. I would like to write the function maybeLoeb :: Functor f => f (f a -> a) -> Maybe (f a) that is the same as loeb, but returns None instead of entering an infinite loop when loeb is given bad input. However, I cannot figure out how to catch the infinite loop exception that only seems to occur sometimes (other times, the program just never terminates). Any ideas?

E.g., maybeLoeb [(!! 1),(!! 0)] :: Maybe [Int] would return None.

Thanks!

[quchen]

Detecting infinite loops means solving the halting problem,

-- Just () if x halts, Nothing if it doesn't
\x -> maybeLoeb [ if halts x then const () else (!! 1), (!! 0) ]

so unfortunately that's not something loeb can do in general.

The problem here is that we're not modeling our recursion inside a language we can reason about within the Haskell program but in Haskell itself, which is Turing-complete, so it suffers from the Halting problem. (A domain-specific language that is limited enough we can investigate it for termination could allow such reasoning, but then there would be algorithms you cannot express in that language.)

[spitis]

Thanks this is very helpful -- I had not known about this halting problem but I have done some minimal reading now and see the problem.

Unfortunately loeb seems not very useful without having at least a somewhat functional maybeLoeb, so I think a solution is a "loeb if does not halt after n self-references". Then Excel's loeb would be be a "loeb if does not halt after 1 self-references". I'll go implement this