"I was struck by the idea of a function taking a function as input and transforming it to another function as output."
That's a higher-order function (HoF). I'd say it's not the fundamental thing to understand about FP: you can even program in a functional way without using them.
And also you can have languages which aren't putting the emphasis on FP at all and yet who have higher-order functions: elisp, for example (anyone calling elisp functional is automatically setq'ed to crazy ; )
IMHO Lisp dialects aren't inherently functionals. Some are, some aren't. Even Clojure, which definitely puts the emphasis on FP, isn't purely functional, far from it. But you can use it in a functional way (and Java too, in a way -- I used to do "OO over immutable objects" and use "functional Java").
However you'll probably find that when using Lisps in a functional way, you can use higher-order function often. For example if you have, say, a referentially transparent function and want to add memoization for free then it's very convenient to simply (memoize myfunc).
Or if you want to "carry the state" of your program through monads (or to use other kind of monads): then you'll need higher-order functions.
To me if there is one thing about FP it is simply idempotent / referentially transparent functions which make it easier to reason about the program.
I'm simply beginning to "grok" FP, HoFs and Clojure so take this with a grain of salt : )
>you can even program in a functional way without using them.
For a very tiny limited subset of programs. Anything beyond the most trivial of toy apps will use them.
>And also you can have languages which aren't putting the emphasis on FP at all and yet who have higher-order functions
Where their usefulness is seriously hampered by the language not being functional. This is the primary reason people think HoFs are no big deal. They've never gotten to actually use them in an environment designed to make good use of them.
That's a higher-order function (HoF). I'd say it's not the fundamental thing to understand about FP: you can even program in a functional way without using them.
And also you can have languages which aren't putting the emphasis on FP at all and yet who have higher-order functions: elisp, for example (anyone calling elisp functional is automatically setq'ed to crazy ; )
IMHO Lisp dialects aren't inherently functionals. Some are, some aren't. Even Clojure, which definitely puts the emphasis on FP, isn't purely functional, far from it. But you can use it in a functional way (and Java too, in a way -- I used to do "OO over immutable objects" and use "functional Java").
However you'll probably find that when using Lisps in a functional way, you can use higher-order function often. For example if you have, say, a referentially transparent function and want to add memoization for free then it's very convenient to simply (memoize myfunc).
Or if you want to "carry the state" of your program through monads (or to use other kind of monads): then you'll need higher-order functions.
To me if there is one thing about FP it is simply idempotent / referentially transparent functions which make it easier to reason about the program.
I'm simply beginning to "grok" FP, HoFs and Clojure so take this with a grain of salt : )