takeoutweight · June 27, 2014 02:55 · Jun 27, 2014
diff --git a/Main.hs b/Main.hs
@@ -0,0 +1,34 @@
+{-# 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!
No results found