Wednesday, March 29, 2017
The Choose Function
In my Haskell code, I chose to represent sets as lists. In practice, this means I have to prevent duplicates in the lists that represent sets. Just to be difficult, I also use lists for ordered pairs of same type things, or maps from index to things. If the things are of different type, then ensuring there are not duplicates is a no-brainer and they might as well be ordered, so I use tuples. This is all very mathematical, and functions resemble constructive proofs. Where computational functions differ from proofs is in which shortcuts are taken. Proofs don't care how long they take to execute. Computer functions are expected to complete in a reasonable time. I use a function called choose to document when I am deviating from the mathematical ideal to make a function more computational. Choose is defined as head; it returns the first element of the list. Choose is intended for use only on lists representing sets, but that is not the only intended restriction on its use. Choose is intended for use when any element of the set would be correct, and the choice of element changes the result of a function it is directly or indirectly used in. Where the choice would not affect the result, I use head. The reason this makes the functions using choice less mathematical and more computational is that the alternative is to return all valid results, not just one valid result. For example, my superSpace function uses choose often to simplify the computational problem, even though the simplest solution to the mathematical problem is that there are multiple solutions.