Note: I don’t like this one much anymore - not that it’s wrong, it just feels like linkedin content.
Posted 2022–05–26.
I remember reading a discussion between two colleagues in the functional programming Slack channel at a workplace.
They were discussing some concept, maybe higher-kinded types. The conversation went something like this:
- A: Oh, what’s a higher-kinded type?
- B: A type with a form like this: [code]
- A: And why would I want that?
- B: It has uses but they’re kinda hard to explain without you first understanding the problems they solve.
- B: You have to show the the wall before you show the ladder.
Knowing this is almost crucial to understanding concepts like those found in functional programming. When we read about some new concept with a mystifying name and an abstract definition, it’s often helpful to understand why people are interested in the first place.
Of course, this doesn’t just apply to functional programming. I was reading about the “WaveFunctionCollapse” algorithm, which is a backtracking algorithm used for extrapolating from an input. I thought I would have a try at implementing it myself. While trying to implement it based on a fairly loose definition I had read, I decided to cut out the “propagating” step and try a simpler backtracking algorithm:
- Pick a tile and set it randomly to one of its possible values
- Make sure it’s not conflicting with any of its neighbours
- If it conflicts, backtrack
- Repeat
This seems to work alright, except in certain cases where the algorithm doesn’t terminate in a reasonable number of generations. As far as I can tell, the “propagating” step should mitigate this by very quickly cutting down the number of possibilities for each tile, giving us a definite result much faster.
I think there’s a somewhat mundane lesson here. As a student, you have to put in the foundational work to understand the problems that justify the higher levels. You’ll probably be rewarded for it with a deeper and more applicable understanding of the domain.
As a teacher, you have to understand this. You have to show the wall before you show the ladder.