Functional Programming - Functions defining specific evaluation of functions passed to it for optimization

Question

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

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?

Answer 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.

Answer 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!