Advertisement
Guest User

two memfib rewrites with LETs

a guest
Feb 22nd, 2020
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ;;https://stackoverflow.com/questions/60331920/partial-application-versus-pattern-matching-why-do-these-haskell-functions-beha#comment106748884_60331920
  2.  
  3. there is no guarantee in the *language* for CAFs to be [memoizing](https://wiki.haskell.org/Memoization#Memoising_CAFS) (i.e. for `theCache` to be pushed over the lambda), AFAIK, it is something GHC implementors decided to do (?).
  4.  
  5. 1.
  6.  
  7. memfib = (!!) (map fib [0..])
  8.   where
  9.     fib 0 = 0
  10.     fib 1 = 1
  11.     fib k = memfib(k-2) + memfib(k-1)
  12.   =
  13.   let  { mapfib = (map fib [0..]) }  in  (!!) mapfib   -- THIS CRUCIAL STEP
  14.       where
  15.         fib 0 = 0
  16.         fib 1 = 1
  17.         fib k = memfib(k-2) + memfib(k-1)
  18.   =  -- where's scope is attached to the definition `memfib =`, so is above all else
  19.    let
  20.     fib 0 = 0
  21.     fib 1 = 1
  22.     fib k = memfib(k-2) + memfib(k-1)
  23.    in
  24.      let { mapfib = (map fib [0..]) }
  25.      in  \n -> (!!) mapfib n               -- eta-expansion NOW
  26.  
  27.   -- fib is above mapfib, scope-wise,
  28.   -- but the two scopes can be squashed together into one LET just the same
  29.  
  30. 2.
  31.  
  32. memfib_wparam = \n -> ((!!) (map fib [0..])) n
  33.   where
  34.     fib 0 = 0
  35.     fib 1 = 1
  36.     fib k = memfib_wparam(k-2) + memfib_wparam(k-1)
  37.  
  38.   = -- where can't be part of lambda, so fib is above the lambda, scope-wise
  39.    let
  40.     fib 0 = 0
  41.     fib 1 = 1
  42.     fib k = memfib_wparam(k-2) + memfib_wparam(k-1)
  43.   in
  44.     \n -> ((!!) (map fib [0..])) n
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement