7

I have a trivial example of SQL-like join for ordered lists: if outer parameter is True then it's union; otherwise it's intersection:

import System.Environment

main = do
  [arg] <- getArgs
  let outer = arg == "outer"
  print $ length $ joinLists outer [1..1000] [1,3..1000]

joinLists :: (Ord a, Num a) => Bool -> [a] -> [a] -> [a]
joinLists outer xs ys = go xs ys
  where
  go [] _ = []
  go _ [] = []
  go xs@(x:xs') ys@(y:ys') = case compare x y of
    LT -> append x $ go xs' ys
    GT -> append y $ go xs ys'
    EQ -> x : go xs' ys'
  append k = if {-# SCC "isOuter" #-} outer then (k :) else id

When I profile it, I see that isOuter condition is evaluated every time when append is called:

stack ghc -- -O2 -prof example.hs && ./example outer +RTS -p && cat example.prof 

                                                     individual      inherited
COST CENTRE MODULE                no.     entries  %time %alloc   %time %alloc
MAIN        MAIN                   44          0    0.0   34.6     0.0  100.0
 isOuter    Main                   88        499    0.0    0.0     0.0    0.0

But I'd like the condition to be evaluated only once, so append in go loop is replaced with either (k :) or id. Can I force it somehow? Is it related to memoization?

EDIT: Seems like I misinterpreted the profiler output. I added trace to append definition:

append k = if trace "outer" outer then (k :) else id

And outer is printed only once.

EDIT2: If I replace append with point-free definition, then if condition is evaluated only once:

 append = if outer then (:) else flip const
11
  • I tried {-# NOINLINE append #-}, to no effect.
    – modular
    Commented Nov 3, 2016 at 18:58
  • 1
    I think you're misreading the output of the profiler. Your cost centre is the condition of the if statement, which is evaluated every time you call append, hence the hits to the cost centre. But the thunk that the outer variable points to is only evaluated once. If you put your cost centre inside arg == "outer" then you should see it only being hit once. Commented Nov 3, 2016 at 19:16
  • If you don't want the if condition to be evaluated multiple times, you could manually float it to the outside of the loop. joinLists outer = go (if outer then (:) else flip const) and redefine go to take an extra argument for append, rather than referring to its closure. I can't predict whether that'd be faster for your inputs. Commented Nov 3, 2016 at 19:20
  • 2
    What happens if you define append like this: append = if outer then (:) else flip const? (I would test it myself, but I don't have GHC here right now.)
    – duplode
    Commented Nov 3, 2016 at 19:23
  • @BenjaminHodgson and duplode thanks for your comments, they practically answer my question (see the edits).
    – modular
    Commented Nov 3, 2016 at 19:34

1 Answer 1

5

I would try pushing lambdas inwards:

append = if {-# SCC "isOuter" #-} outer then \k -> (k :) else \k -> id

The original code is essentially \k -> if outer ... which takes the argument first, and tests the guard later. The code above instead tests the guard before taking the argument.

Alternative:

append | outer     = \k -> (k :) 
       | otherwise = \k -> id

One can further simplify those lambdas to a more readable form.

1
  • As an aside, \k -> (k :) is just (:), but I like the symmetry with \k -> id (rather than const id).
    – Jon Purdy
    Commented Nov 3, 2016 at 20:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.