4

Firstmost, I am just getting started with functional programming so I would appreciate corrections in any terminology I may have used incorrectly.

Story time, While doing a Project Euler Problem 1 in Haskell I came to a solution that look roughly like

sum [3,6..999] + sum [5,10..999] - sum[15,30..999]

Which each sum is evaluated into

foldl (+) [x1,x2,x3,x4,x5,x6,etc] -- yep, the sum is evaluated one element at a time  

So, my understanding is that lazy evaluation means that sum(2) could be optimized to pattern match the Enumeration(3) so that instead of folding it could optimize for special cases such as sum i from 1 to n = n*(n+1)/2

However, at least in Haskell, you cannot pattern match and grab the arguments from another function. The basic idea would be whether sum should be intelligent enough to recognize known mathematical formula for optimization of calculation by evaluating other functions itself:

-- Doesn't work; didn't intend to; not valid Haskell
-- Try known formulas first if the list generator is known
-- This would match sum [1..100] and return 5050 in O(1)
sum `EnumFromTo` 1 n = n*(n+1)/2
-- If the sum is not recognized then it would do it 1 by 1 as a fallback in O(n)
-- This is the current and only implementation of sum
sum = foldl (+) 0

I would guess it would be easier, more straightforward, and betterstyle to define a new sum function with a different name that covers the given formula such as

sumTo n
    | n >= 1 = n*(n+1)/2

But conceptually speaking

  • Is redefining specific functions from within another function possible?
  • Would allowing this break something?(IE, in this case, "EnumFromTo 1 n" would not be evaluated, but sum would still return the correct result)
  • Are there any examples of this evaluation scheme?
  • Is this a concept any programming language implements?
  • If someone votes to close, could I know why? I thought this was on topic here, or should I have asked over at Computer Science or Theoretical Computer Science? (Honest question, would gladly have it moved to a place where I can get an answer) – Fabián Heredia Montiel May 26 '15 at 21:12
  • Ok, I think this should be more readable/clearer. Please let me know of anything else I can improve. – Fabián Heredia Montiel May 26 '15 at 22:03
  • Another comment: This is probably an XY Problem since I already know I could create a new function that knows this formula. But! this is more in the vain on the possibility and merit of sum being intelligent about what it evaluates and how. – Fabián Heredia Montiel May 26 '15 at 22:11
1

Because of the way the expression is parsed and evaluated, a sum function will get the results of the EnumFromTo, and therefore under normal conditions there is no way to get at its arguments.

To receive the unevaluated arguments, you would need to use a macro. I don't know anything about Template Haskell, but supposedly it provides this ability. In practice, macros are notoriously difficult to use outside of homoiconic languages like LISP. The laziness of Haskell also removes a lot of the cases where macros would be useful. Your sumTo function is much easier to implement, so that's what people will use.

-2

Check this (Clojure code, sorry I don't know Haskell):

(declare m-enum-upto)

(defn enum-upto [n]
  (cond
    (= n 0) 0
    (= n 1) 1
    :else (+ n (m-enum-upto (dec n)))))

(def m-enum-upto (memoize enum-upto))

; at the first run 
(enum-upto 5) ; 0.497711 msec
;again
(enum-upto 5); 0.1130686 msec
;and now
(enum-upto 3); 0.09372 msec
(enum-upto 30); 0.883901 msec
(enum-upto 5); 0.100872 msec
(enum-upto 20); 0.100515 msec

The trick is using memoize, it use a cache for storing enum-upto's values. This way only new values have to be calculated.

or you could use reducers:

(defn r-enum-upto [n] (reduce + (map inc (range n))))

(r-enum-upto 200); 0.18883 msec (r-enum-upto 200000); 43.050614 msec

I hope it helps!

  • 1
    Programmers is about conceptual questions and answers are expected to explain things. Throwing code dumps instead of explanation is like copying code from IDE to whiteboard: it may look familiar and even sometimes be understandable, but it feels weird... just weird. Whiteboard doesn't have compiler – gnat May 26 '15 at 21:26
  • Sorry, the idea is that pure functions can be exchanged by its values since there are no side effects. – Leonardo Gomez May 26 '15 at 21:45
  • Sorry for the confusion Leonardo I wasn't quite asking about better performance per se, I redacted my question to be clearer. – Fabián Heredia Montiel May 26 '15 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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