Advertisement
Guest User

two memfib rewrites with LETs

a guest
Feb 22nd, 2020
134
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.   =
  19.    -- where's scope is attached to the definition `memfib =`, so is above all else
  20.   let
  21.     fib 0 = 0
  22.     fib 1 = 1
  23.     fib k = memfib(k-2) + memfib(k-1)
  24.    in
  25.      let { mapfib = (map fib [0..]) }
  26.      in  \n -> (!!) mapfib n               -- eta-expansion NOW
  27.  
  28.   -- fib is above mapfib, scope-wise, but the two scopes
  29.   -- can be squashed together into one LET just the same
  30.  
  31. 2.
  32.  
  33. memfib_wparam -- n =  ((!!) (map fib [0..])) n
  34.               = \n -> ((!!) (map fib [0..])) n    -- parameter syntax is sugar for lambdas
  35.   where
  36.     fib 0 = 0
  37.     fib 1 = 1
  38.     fib k = memfib_wparam(k-2) + memfib_wparam(k-1)
  39.   =
  40.   -- where can't be part of lambda, so fib is above the lambda, scope-wise
  41.    let
  42.     fib 0 = 0
  43.     fib 1 = 1
  44.     fib k = memfib_wparam(k-2) + memfib_wparam(k-1)
  45.   in
  46.     \n -> ((!!) (map fib [0..])) n
  47.                 --------------
  48.                 -- -CSE could float this too, if it chose to !
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement