Skip to content

Redex pushed under a lambda -- yikes!

Consider this program

{-# LANGUAGE UnboxedTuples #-}

module Foo where

data T = MkT !Int Int

g :: Int -> (# Int, Int #)
g 0 = (# 44, 33 #)
g n = g (n-1)

womble :: (Int->T) -> [Int] -> [T]
{-# NOINLINE womble #-}
womble f xs = map f xs

f :: Int -> [Int] -> [T]
f x xs = womble (MkT (case g x of (# a,b #) -> a)) xs

Suppose g is arbitrarily expensive; here it is just a loop.

You'd expect that case expression to be evaluated just once for each call of f. But the code we get is

f = \ (x_aww :: Int) (xs_awx :: [Int]) ->
      womble
        (\ (ds_dK2 :: Int) ->
           case x_aww of { GHC.Types.I# ww1_sKE ->
           case Foo.$wg ww1_sKE of { (# ipv_sKw, ipv1_sKx #) ->
           Foo.$WMkT ipv_sKw ds_dK2
           }
           })
        xs_awx

Yikes! g is called once for each element of xs. This is Utterly Wrong.

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information