5 ms·

So did anyone else look at the challenge problem, see f(n-3), f(n-2), and f(n-1), then immediately think "oh. A three element array would solve that"? Took me l

by palish 15y ago

So did anyone else look at the challenge problem, see f(n-3), f(n-2), and f(n-1), then immediately think "oh. A three element array would solve that"? Took me less than 60 seconds... I'm a little worried that I'm so good at imperative programming, though, since it might indicate that I'm "crippled" when it comes to functional programming. I bet one of you could code circles around me when it comes to e.g. implementing a DSL. Anyone have advice about how I'd go about "diving into functional programming"? What's a fun project to do in Haskell, for example? I rarely approach a programming problem by trying to define functional routines. Instead, I almost always use state. Seems like a bad habit that I need to focus on breaking.

mightybyte 15y ago
Dive into Haskell with whatever interests you. Try solving some Project Euler problems (http://projecteuler.net http://projecteuler.net). Or, maybe web programming suits your fancy (http://snapframework.com http://snapframework.com). If you're more visual you might play around with these exercises which don't even require you to install anything. http://pnyf.inf.elte.hu/fp/FunctionGraphs_en.xml http://pnyf.inf.elte.hu/fp/FunctionGraphs_en.xml http://pnyf.inf.elte.hu/fp/Diagrams_en.xml http://pnyf.inf.elte.hu/fp/Diagrams_en.xml Others here: http://pnyf.inf.elte.hu/fp/Overview_en.xml http://pnyf.inf.elte.hu/fp/Overview_en.xml
- palish 15y ago
  Thanks!
colanderman 15y ago
I looked at it and thought, "easy, I'll just rewrite the Scheme function in Mercury and tell the compiler to memoize the function." Of course, obviously the point of the exercise is to encourage thinking about how a computer actually performs computations, which is in a linear, imperative fashion. In that case, why use Scheme in the first place? Its syntax and semantics encourage exactly the opposite style of programming, and in my opinion, obstruct the learning process in this kind of problem. To make an analogy, teaching this problem using Scheme is like teaching someone how to bake a cake using an unplugged Kitchenaid. The Kitchenaid would work great if it was plugged in, but it's not, so you have to push the beater around by hand. Why not just use a hand beater in the first place? [Scheme would work great for this problem if it had memoization, but it doesn't, so you have to solve the problem as if you were using Python. Why not just use Python in the first place?]
- yoklov 15y ago
  The point of Scheme isn't to provide you with a given feature like memoization, its to provide you with the tools so you can do it yourself. SICP covers memoization at the end chapter 3.3.3 (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec_3.3.3 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html...): (define (memoize f) (let ((table (make-table))) (lambda (x) (let ((previously-computed-result (lookup x table))) (or previously-computed-result (let ((result (f x))) (insert! x result table) result))))))
  - beza1e1 15y ago
    And SICP quits at this point? What if "previously-computed-result" is false, because f computes boolean values? This is just an 80% solution, which works for "fib".
    - yoklov 15y ago
      The implementation of tables that he uses isn't actually reasonable for most use. If actually implementing memoization, one would probably use SFRI-44 style maps, which come with a 'contains-key' function that solves this problem.
  - colanderman 15y ago
    The same could be said of any Turing-complete language (though I'll admit Scheme's macro system gives it a leg up when it comes to implementing new features.) But given that Scheme's syntax encourages thinking in terms of mathematical recursion, it seems silly that (a) I can't write something so simple as the Fibonacci function by using its traditional mathematical recursive definition, and that (b) SICP encourages the use of Scheme to solve problems which require thinking in terms of iteration and mutation -- this is a pedagogical faux pas.
    - yoklov 15y ago
      The difference between Scheme and any "Turing complete language", is the philosophy behind it, which is one of minimalism. That's why memoization isn't implemented for you. Scheme was also designed to encourage implementing non-recursive control structures, as well as programming with side effects. Scheme isn't supposed to be totally pure. If you encounter a problem that requires mutation, you're supposed to try to abstract away from the mutation, if possible, and it gives you the tools to do that. (first class functions, macros, continuations, etc. are all very effective tools for abstraction, once you learn them.) I recommend that you use SICP to learn Scheme, as it will make more sense when you actually know how to use it. It's an incredibly elegant and beautiful language, and it's certainly still relevant. P.S. If you're thinking of those problems in terms of iteration and mutation, you're probably doing it wrong :). Think more functionally.
pavpanchekha 15y ago
Just sit down and start coding in Haskell. Not that Haskell is the world's best langauge or anything, but it strictly enforces a functional mode of thought, and that's what you want if you want to be forced to program functionally.
chewbranca 15y ago
A great way to dive into functional programming is to read the book that this topic discusses.
Goladus 15y ago
> Anyone have advice about how I'd go about "diving into functional programming"? http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/ http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussma...
vii 15y ago
Well a three element array does solve that but there are better ways still. http://www.starling-software.com/blogimg/tsac/1011/fremlin-tsac-2008-11-28.pdf http://www.starling-software.com/blogimg/tsac/1011/fremlin-t... In my opinion the idea that there is a division between functional and non-functional programming at all comes because of a disagreement or misunderstanding with the principles of SICP: C is a perfectly functional programming language if you say that each statement is a function from machine state to machine state. . .
yummyfajitas 15y ago
What's a fun project to do in Haskell, for example? I recommend a project with lots of IO and State. You'll quickly come to understand why the monadic approach to such things is excellent (even if Haskell's implementation is a bit verbose).

by palish 15y ago

mightybyte 15y ago

Dive into Haskell with whatever interests you. Try solving some Project Euler problems (http://projecteuler.net http://projecteuler.net). Or, maybe web programming suits your fancy (http://snapframework.com http://snapframework.com). If you're more visual you might play around with these exercises which don't even require you to install anything. http://pnyf.inf.elte.hu/fp/FunctionGraphs_en.xml http://pnyf.inf.elte.hu/fp/FunctionGraphs_en.xml http://pnyf.inf.elte.hu/fp/Diagrams_en.xml http://pnyf.inf.elte.hu/fp/Diagrams_en.xml Others here: http://pnyf.inf.elte.hu/fp/Overview_en.xml http://pnyf.inf.elte.hu/fp/Overview_en.xml

palish 15y ago
Thanks!

colanderman 15y ago

I looked at it and thought, "easy, I'll just rewrite the Scheme function in Mercury and tell the compiler to memoize the function." Of course, obviously the point of the exercise is to encourage thinking about how a computer actually performs computations, which is in a linear, imperative fashion. In that case, why use Scheme in the first place? Its syntax and semantics encourage exactly the opposite style of programming, and in my opinion, obstruct the learning process in this kind of problem. To make an analogy, teaching this problem using Scheme is like teaching someone how to bake a cake using an unplugged Kitchenaid. The Kitchenaid would work great if it was plugged in, but it's not, so you have to push the beater around by hand. Why not just use a hand beater in the first place? [Scheme would work great for this problem if it had memoization, but it doesn't, so you have to solve the problem as if you were using Python. Why not just use Python in the first place?]

yoklov 15y ago
The point of Scheme isn't to provide you with a given feature like memoization, its to provide you with the tools so you can do it yourself. SICP covers memoization at the end chapter 3.3.3 (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec_3.3.3 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html...): (define (memoize f) (let ((table (make-table))) (lambda (x) (let ((previously-computed-result (lookup x table))) (or previously-computed-result (let ((result (f x))) (insert! x result table) result))))))
- beza1e1 15y ago
  And SICP quits at this point? What if "previously-computed-result" is false, because f computes boolean values? This is just an 80% solution, which works for "fib".
  - yoklov 15y ago
    The implementation of tables that he uses isn't actually reasonable for most use. If actually implementing memoization, one would probably use SFRI-44 style maps, which come with a 'contains-key' function that solves this problem.
- colanderman 15y ago
  The same could be said of any Turing-complete language (though I'll admit Scheme's macro system gives it a leg up when it comes to implementing new features.) But given that Scheme's syntax encourages thinking in terms of mathematical recursion, it seems silly that (a) I can't write something so simple as the Fibonacci function by using its traditional mathematical recursive definition, and that (b) SICP encourages the use of Scheme to solve problems which require thinking in terms of iteration and mutation -- this is a pedagogical faux pas.
  - yoklov 15y ago
    The difference between Scheme and any "Turing complete language", is the philosophy behind it, which is one of minimalism. That's why memoization isn't implemented for you. Scheme was also designed to encourage implementing non-recursive control structures, as well as programming with side effects. Scheme isn't supposed to be totally pure. If you encounter a problem that requires mutation, you're supposed to try to abstract away from the mutation, if possible, and it gives you the tools to do that. (first class functions, macros, continuations, etc. are all very effective tools for abstraction, once you learn them.) I recommend that you use SICP to learn Scheme, as it will make more sense when you actually know how to use it. It's an incredibly elegant and beautiful language, and it's certainly still relevant. P.S. If you're thinking of those problems in terms of iteration and mutation, you're probably doing it wrong :). Think more functionally.

pavpanchekha 15y ago

Just sit down and start coding in Haskell. Not that Haskell is the world's best langauge or anything, but it strictly enforces a functional mode of thought, and that's what you want if you want to be forced to program functionally.

chewbranca 15y ago

A great way to dive into functional programming is to read the book that this topic discusses.

Goladus 15y ago

> Anyone have advice about how I'd go about "diving into functional programming"? http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/ http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussma...

vii 15y ago

Well a three element array does solve that but there are better ways still. http://www.starling-software.com/blogimg/tsac/1011/fremlin-tsac-2008-11-28.pdf http://www.starling-software.com/blogimg/tsac/1011/fremlin-t... In my opinion the idea that there is a division between functional and non-functional programming at all comes because of a disagreement or misunderstanding with the principles of SICP: C is a perfectly functional programming language if you say that each statement is a function from machine state to machine state. . .

yummyfajitas 15y ago

What's a fun project to do in Haskell, for example? I recommend a project with lots of IO and State. You'll quickly come to understand why the monadic approach to such things is excellent (even if Haskell's implementation is a bit verbose).