# HG changeset patch # User Steve Losh # Date 1320024432 14400 # Node ID d33b3af9c5365d9f7963da74f1348a4787bb1119 # Parent e6267718ee3c720c96fc77733d799492def1c973 Oh god. diff -r e6267718ee3c -r d33b3af9c536 chapters/39.markdown --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/chapters/39.markdown Sun Oct 30 21:27:12 2011 -0400 @@ -0,0 +1,228 @@ +Functional Programming +====================== + +We're going to take a short break now to talk about a style of programming you +may have heard of: [functional programming][]. + +If you've programmed in languages like Python, Ruby or Javascript, or +*especially* Lisp, Scheme, Clojure or Haskell, you're probably familiar with the +idea of using functions as variables and using data structures with immutable +state. If you've never done this before you can safely skip this chapter, but +I'd encourage you to try it anyway and broaden your horizons! + +Vimscript has all the pieces necessary to program in a kind-of-functional style, +but it's a bit clunky. We can create a few helpers that will make it less +painful though. + +Go ahead and create a `functional.vim` file somewhere so you don't have to keep +typing everything over and over. This file will be our scratchpad for this +chapter. + +[functional programming]: https://secure.wikimedia.org/wikipedia/en/wiki/Functional_programming + +Immutable Data Structures +------------------------- + +Unfortunately Vim doesn't have any immutable collections like Clojure's vectors +and maps built-in, but by creating some helper functions we can fake it to some +degree. + +Add the following function to your file: + + function! Sorted(l) + let new_list = deepcopy(a:l) + call sort(new_list) + return new_list + endfunction + +Source and write the file, then run `:echo Sorted([3, 2, 4, 1])` to try it out. +Vim echoes `[1, 2, 3, 4]`. + +How is this different from simply calling the built-in `sort()` function? The +key is the first line: `let new_list = deepcopy(a:l)`. Vim's `sort()` sorts the +list *in place*, so we first create a full copy of the list and sort *that* so +the original list won't be changed. + +This prevents side effects and helps us write code that is easier to reason +about and test. Let's add a few more helper functions in this same style: + + function! Reversed(l) + let new_list = deepcopy(a:l) + call reverse(new_list) + return new_list + endfunction + + function! Append(l, val) + let new_list = deepcopy(a:l) + call add(new_list, a:val) + return new_list + endfunction + + function! Assoc(l, i, val) + let new_list = deepcopy(a:l) + let newlist[a:i] = a:val + return new_list + endfunction + + function! Pop(l, i) + let new_list = deepcopy(a:l) + call remove(new_list, a:i) + return new_list + endfunction + +Each of these functions is exactly the same except for the middle line and the +arguments they take. Source and write the file and try them out on a few lists. + +`Reversed()` takes a list and returns a new list with the elements reversed. + +`Append()` returns a new list with the given value appended to the end of the +old one. + +`Assoc()` (short for "associate") returns a new list, with the element at the +given index replaced by the new value. + +`Pop()` returns a new list with the element at the given index removed. + +Functions as Variables +---------------------- + +Vimscript supports using variables to store functions, but the syntax is a bit +obtuse. Run the following commands: + + :let Myfunc = function("Append") + :echo Myfunc([1, 2], 3) + +Vim will display `[1, 2, 3]` as expected. Notice that the variable we used +started with a capital letter. If a Vimscript variable refers to a function it +must start with a capital letter. + +Functions can be stored in lists just like any other kind of variable. Run the +following commands: + + :let funcs = [function("Append"), function("Pop")] + :echo funcs[1](['a', 'b', 'c'], 1) + +Vim displays `['a', 'c']`. The `funcs` variable does *not* need to start with +a capital letter because it's storing a list, not a function. The contents of +the list don't matter at all. + +Higher-Order Functions +---------------------- + +Let's create a few of the most commonly-used higher-order functions. If you're +not familiar with that term, higher-order functions are functions that take +*other* functions and do something with them. + +We'll begin with the trusty "map" function. Add this to your file: + + function! Mapped(fn, l) + let new_list = deepcopy(a:l) + call map(new_list, string(a:fn) . '(v:val)') + return new_list + endfunction + +Source and write the file, and try it out by running the following commands: + + :let mylist = [[1, 2], [3, 4]] + :echo Mapped(function("Reversed"), mylist) + +Vim displays `[[2, 1], [4, 3]]`, which is the results of applying `Reversed()` +to every element in the list. + +How does `Mapped()` work? Once again we create a fresh list with `deepcopy()`, +do something to it, and return the modified copy -- nothing new there. The +tricky part is the middle. + +`Mapped()` takes two arguments: a funcref (Vim's term for "variable holding +a function") and a list. We use the built-in `map()` function to perform the +actual work. Read `:help map()` now to see how it works. + +Now we'll create a few other common higher-order functions. Add the following to +your file: + + function! Filtered(fn, l) + let new_list = deepcopy(a:l) + call filter(new_list, string(a:fn) . '(v:val)') + return new_list + endfunction + +Try `Filtered()` out with the following commands: + + :let mylist = [[1, 2], [], ['foo'], []] + :echo Filtered(function('len'), mylist) + +Vim displays `[[1, 2], ['foo']]`. + +`Filtered()` takes a predicate function and a list. It returns a copy of the +list that contains only the elements of the original where the result of calling +the function on it is "truthy". In this case we use the built-in `len()` +function, so it filters out all the elements whose length is zero. + +Finally we'll create the counterpart to `Filtered()`: + + function! Removed(fn, l) + let new_list = deepcopy(a:l) + call filter(new_list, '!' . string(a:fn) . '(v:val)') + return new_list + endfunction + +Try it out just like we did with `Filtered()`: + + :let mylist = [[1, 2], [], ['foo'], []] + :echo Removed(function('len'), mylist) + +Vim displays `[[], []]`. `Removed()` is like `Filtered()` except it only keeps +elements where the predicate function does *not* return something truthy. + +The only difference in the code is the single `'!' . ` we added to the call +command, which negates the result of the predicate. + +Performance +----------- + +You might be thinking that copying lists all over the place is wasteful, since +Vim has to constantly create new copies and garbage collect old ones. + +If so: you're right! Vim's lists don't support the same kind of structural +sharing as Clojure's vectors, so all those copy operations can be expensive. + +Sometimes this will matter. If you're working with enormous lists, things can +slow down. In real life, though, you might be surprised at how little you'll +actually notice the difference. + +Consider this: as I'm writing this chapter my Vim program is using about 80 +megabytes of memory (and I have a *lot* of plugins installed). My laptop has +8 *gigabytes* of memory in it. Is the overhead of having a few copies of a list +around really going to make a noticeable difference? Of course that depends on +the size of the list, but in most cases the answer will be "no". + +To contrast, my Firefox instance with five tabs open is currently using 1.22 +*gigabytes* of RAM. + +You'll need to use your own judgement about when this style of programming +creates unacceptably bad performance. I'd *strongly* encourage you to at least +give it a fair try though. Using immutable data structures and higher order +functions can greatly simplify your code and eliminate lots of state-related +bugs. + +Exercises +--------- + +Read `:help sort()`. + +Read `:help reverse()`. + +Read `:help copy()`. + +Read `:help deepcopy()`. + +Read `:help map()` if you haven't already. + +Read `:help function()`. + +Modify `Assoc()`, `Pop()`, `Mapped()`, `Filtered()` and `Removed()` to support +dictionaries. You'll probably need `:help type()` for this. + +Implement `Reduced()`. + +Pour yourself a glass of your favorite drink. This chapter was intense! diff -r e6267718ee3c -r d33b3af9c536 outline.org --- a/outline.org Wed Oct 26 20:42:24 2011 -0400 +++ b/outline.org Sun Oct 30 21:27:12 2011 -0400 @@ -35,7 +35,8 @@ ** DONE lists ** DONE looping ** DONE dictionaries -** TODO toggling +** DONE toggling +** DONE functional programming ** TODO advanced regexes ** TODO paths ** TODO exceptions