http://www.haskell.org/haskellwiki/index.php?title=Data_structures_not_functions&feed=atom&action=historyData structures not functions - Revision history2014-09-16T17:37:22ZRevision history for this page on the wikiMediaWiki 1.19.5-1+deb7u1http://www.haskell.org/haskellwiki/index.php?title=Data_structures_not_functions&diff=22593&oldid=prevAndrewBromage: Creating page2008-08-25T01:58:00Z<p>Creating page</p>
<p><b>New page</b></p><div>[[Category:Idioms]]<br />
<br />
Sometimes the best way to implement a function is as a data structure. You can then implement a lightweight interpreter which "executes" the data structure.<br />
<br />
There are many examples of this in Haskell code, but a simple one is algorithms which iterate until some condition is met. A good way to implement this is as an [[infinite stream]] of results, which is passed to an "interpreter" which selects which result is the most appropriate.<br />
<br />
Rather than this loop:<br />
<br />
<haskell><br />
squareRoot n = squareRoot' n (initialGuess n)<br />
where<br />
squareRoot' x<br />
| closeEnough x = x<br />
| otherwise = squareRoot' (0.5 * (x + n/x))<br />
</haskell><br />
<br />
write this:<br />
<br />
<haskell><br />
squareRoot n = head . filter closeEnough $ squareRoot' n (initialGuess n)<br />
<br />
squareRoot' n x = iterate (\x -> 0.5 * (x + n/x)) x<br />
</haskell><br />
<br />
There are several advantages to using this approach :<br />
<br />
* This is easier to test and debug, because the [[intermediate form]] doubles as an execution trace.<br />
* There is a clean [[separation of responsibilities]]. If someone wants to use the algorithm with a different "close enough" test, or a better initial guess, it's easy to do.<br />
<br />
Interestingly, if you implement this using standard list functions, such as head, filter and iterate, there may be no performance penalty. If the compiler uses a modern deforestation optimization, such as [[stream fusion]], the intermediate data structure will be compiled away.<br />
<br />
A more sophisticated (but not necessarily much more complex) application of this idiom is the [[GADT]] approach to [[prototyping monads]].<br />
<br />
You can also use [[functions not data structures]].<br />
<br />
[[User:AndrewBromage]]</div>AndrewBromage