4 ms·
I would argue that there's no such thing as a "functional data structure." If a data structure maps poorly to existing functional languages, that's a symptom of
by smitherfield 10y ago
I would argue that there's no such thing as a "functional data structure." If a data structure maps poorly to existing functional languages, that's a symptom of an insufficiently powerful and generic type system.
Say you have (pseudocode)
Array(4 16 5 20)
What's its type?
Array
Array<Int>
Array<4>
Array<Int 4>
Array(Int Int Int Int)
None of these lend themselves easily to paradigms other than imperative, true. But this is because they unnecessarily discard known information. The type of an array ought to be itself:
assert Array(4 16 5 20) hasType Array(4 16 5 20)
=> Ok
assert Array(4 16 5 20) hasType Array<Int>
=> Error("Expected Array<Int> but got Array(4 16 5 20). Hint: Typeclass Array<Int> cannot be directly instantiated")
assert Array(4 16 5 20) hasTypeclass Array<Int>
=> Ok
Fully functional and referentially transparent.
- DonaldFisk 10y agoAnd if you want a new array whose first element is increased by one, you either have to allocate space for the entire array, modify the array, or use a different data structure.
- smitherfield 10y agoNo you don't, you merely need each index into an array to be a monad over all possible values it can contain. An array is itself and modifications are (take as arguments and return) its indices.
- DonaldFisk 10y agoAnd how is that implemented under the hood?
- smitherfield 10y agoSame as in a higher-level statically typed imperative language: mutable arrays contained within larger dynamic buffers for amoritized constant-time append and prepend.
- DonaldFisk 10y agoSo it isn't really functional at all. It just hides the side effects behind a lot of complexity.
- junke 10y agoThis is precisely what functional programming does. Purely functional abstractions are just that, abstractions.
- kazinator 10y ago> you merely need each index into an array to be a monad over all possible values it can contain Now keep a straight face and say "L1 cache" once again.