Created
June 27, 2014 02:55
-
-
Save takeoutweight/e104fb3c76f1f599dc5c to your computer and use it in GitHub Desktop.
Haste might seem like it has TCO, but it doesn't.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{-# LANGUAGE BangPatterns #-} | |
module Main where | |
-- This is constant space. Haste's Inlining (via GHC frontend) seems to | |
-- be able to combine even+odd to give us a single, tail-recursive loop. | |
even' :: Int -> Bool | |
even' 0 = True | |
even' !x = odd' (x - 1) | |
odd' :: Int -> Bool | |
odd' 0 = False | |
odd' !x = even' (x - 1) | |
-- GHC frontend can't inline these into a tail-recursive loop, | |
-- So we need full TCO, which Haste/JS doesn't give us. | |
-- Runs fine with GHC, but w/ Haste we blow the JS stack just on 3,000 :( | |
-- handwritten Javascript impl of the same takes 14,000 to blow JS stack. | |
table = [even'', odd''] | |
even'' :: Int -> Int -> Bool | |
even'' !lu 0 = True | |
even'' !lu !x = (table !! lu) 0 (x - 1) | |
odd'' :: Int -> Int -> Bool | |
odd'' !lu 0 = False | |
odd'' !lu !x = (table !! lu) 1 (x - 1) | |
main :: IO () | |
main = do | |
-- putStrLn (show (even'' 1 3000)) -- blows stack! | |
putStrLn (show (even' 1000000)) -- OK! |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment