3 ms·

Manipulating lists is a solved problem in functional programming IMO, but I struggle to define good higher-order tree operations. Complex operators compose very

by ced 14y ago

Manipulating lists is a solved problem in functional programming IMO, but I struggle to define good higher-order tree operations. Complex operators compose very poorly, and have too many options. So instead I write many simple operators, most of which I don't use frequently enough to remember that they exist at all. Or, I just give up and use recursion.

mattmight 14y ago
Stay tuned. That's a major topic in my compilers class, and I'll likely write a post on that as well. In the meantime, I recommend you check out "Scrap Your Boilerplate" in Haskell.
- tel 14y ago
  SYB is basically required reading... but Uniplate is much easier to grasp at first, I feel.
- cgag 14y ago
  Is there any chance of you ever doing your compilers class on Coursera or just posting videos of the lectures online somewhere? Your blog posts are great, I'd love to be able to see the lectures as well.
  - mattmight 14y ago
    Thanks for the kind words! I don't know if my teaching style would translate well to Coursera or Udacity. My classes tend to be very interactive. Assuming I recorded in front of a live class, some of that would come across. But, it would lose some of the spontaneity that comes from sitting in the class and being able to interject. I do post my (unanimated) lecture slides online as pdfs.
dxbydt 14y ago
> I give up and use recursion. Well, trees are recursive. Sometimes the cost bugs me, so I implement the tree as a list of lists ( each level in tree is its own list) ... this brings costs down but the code looks nasty and lot more bookkeeping under the hood. If anything, I've fallen in love with recursion all over again...it is so bloody natural
tikhonj 14y ago
Maps and folds, at the very least, generalize to trees fairly naturally. They also behave essentially the same way as for lists. If you want more versatile functions, you could look at the famous "Bananas, Envelopes, Lenses and Barbed Wire" paper which introduces a bunch of recursion schemes that apply to trees as well as lists and other structures. These have Greek names you might have heard like "catamorphism" (a generalized fold). Even if you don't end up using the functions, it's a good read. Might be a bit dense though, but it's not that bad or terribly heavy on math.

by ced 14y ago

mattmight 14y ago

Stay tuned. That's a major topic in my compilers class, and I'll likely write a post on that as well. In the meantime, I recommend you check out "Scrap Your Boilerplate" in Haskell.

tel 14y ago
SYB is basically required reading... but Uniplate is much easier to grasp at first, I feel.
cgag 14y ago
Is there any chance of you ever doing your compilers class on Coursera or just posting videos of the lectures online somewhere? Your blog posts are great, I'd love to be able to see the lectures as well.
- mattmight 14y ago
  Thanks for the kind words! I don't know if my teaching style would translate well to Coursera or Udacity. My classes tend to be very interactive. Assuming I recorded in front of a live class, some of that would come across. But, it would lose some of the spontaneity that comes from sitting in the class and being able to interject. I do post my (unanimated) lecture slides online as pdfs.

dxbydt 14y ago

> I give up and use recursion. Well, trees are recursive. Sometimes the cost bugs me, so I implement the tree as a list of lists ( each level in tree is its own list) ... this brings costs down but the code looks nasty and lot more bookkeeping under the hood. If anything, I've fallen in love with recursion all over again...it is so bloody natural

tikhonj 14y ago

Maps and folds, at the very least, generalize to trees fairly naturally. They also behave essentially the same way as for lists. If you want more versatile functions, you could look at the famous "Bananas, Envelopes, Lenses and Barbed Wire" paper which introduces a bunch of recursion schemes that apply to trees as well as lists and other structures. These have Greek names you might have heard like "catamorphism" (a generalized fold). Even if you don't end up using the functions, it's a good read. Might be a bit dense though, but it's not that bad or terribly heavy on math.