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

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?
• 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) Commented May 26, 2015 at 21:12
• Ok, I think this should be more readable/clearer. Please let me know of anything else I can improve. Commented May 26, 2015 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. Commented May 26, 2015 at 22:11

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.

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!

• 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
Commented May 26, 2015 at 21:26
• Sorry, the idea is that pure functions can be exchanged by its values since there are no side effects. Commented May 26, 2015 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. Commented May 26, 2015 at 22:05