> Haskell is not actually a completely 'safe' language; it still has exceptions that can cause a program to "go wrong" and terminate unexpectedly. You can write 'fast' code with it, but it isn't as fast as what I could write in a lower-level language.
I never meant to imply Haskell was a "completely safe" language. That is an impossibility, even totality does not imply complete safety. My zip example is actually a point against Haskell (as length-indexed lists are not yet actually in use in the Haskell eco-system).
Haskell can encode low-level programs that are almost C-level, and in that (ugly) style can probably reach the performance you can with lower-level languages (excluding hand-optimized assembly, perhaps).
> As the data structures get further away from algebraic data types, the type hackery gets more and more involved. If you start working with arbitrary mutable data structures that arise in practice, the type hackery becomes a topic for a PhD thesis rather than something usable in practical programming today.
Mutable data structures do not have to "arise in practice". You can have pure semantics with mutable performance (e.g: Clean's uniqueness types, or Haskell's ST).
Lots of people's PhD thesis are in actual use in practical programming today. A PhD thesis often discovers a technique and makes it accessible for real world programs today.
> I don't know of any compiler that actually does a reasonable job converting uses of data structures like lists and association lists into arrays and hash tables in general. I think this falls into the territory of the "sufficiently smart compiler" fallacy.
Converting these is not a good idea because you would change the complexities of the code (which is, IMO, the heart of the fallacy). A prepend of an a-list or a list is O(1), but to a list or hash table, it is (in the worst-case) worse.
But what Haskell's primary compiler, GHC, does do, is fuse together list processing such that lists can disappear altogether into efficient loops.
As for arrays and hash tables, these are not amenable to efficient "pure" modification (unless you use uniqueness types as in Clean), but they have reasonable alternatives that are pure and persistent: Sequence allows O(logN) indexing, O(1) amortized (O(logN) worst-case) prepend/append. Tries and search trees allow for quick lookups and quick pure modification. These are easy to reason about.
> Also, making data contiguous is just the simplest of a common set of data representation optimizations.
This conflicts with O(1) prepend. If you want contiguous allocation, you can use different data structures.
> Does any compiler automatically convert a list into an intrusive doubly linked list or eliminate the use of a visited stack for DFS by stealing a bit from vertices or reversing pointers?
If you need to remove/insert items in the middle of a list, you would probably not use a linked list. So a doubly linked is not a good optimization to apply automatically.
If your point is that code with simpler mathematical semantics that is easy to reason about might cause a constant hit on performance in some cases -- then I agree. You cannot always have simplicity, verifiability, and speed. But often you can.
Also note that purity affords many optimizations that are unavailable in non-pure languages (e.g: rewrite rules like: map f . map g --> map (f . g)).
O(1) prepend doesn't conflict with good contiguity at all. Deque is an useful data structure with (possibly amortised) O(1) prepend and append, O(1) indexing and excellent contiguity.
I never meant to imply Haskell was a "completely safe" language. That is an impossibility, even totality does not imply complete safety. My zip example is actually a point against Haskell (as length-indexed lists are not yet actually in use in the Haskell eco-system).
Haskell can encode low-level programs that are almost C-level, and in that (ugly) style can probably reach the performance you can with lower-level languages (excluding hand-optimized assembly, perhaps).
> As the data structures get further away from algebraic data types, the type hackery gets more and more involved. If you start working with arbitrary mutable data structures that arise in practice, the type hackery becomes a topic for a PhD thesis rather than something usable in practical programming today.
Mutable data structures do not have to "arise in practice". You can have pure semantics with mutable performance (e.g: Clean's uniqueness types, or Haskell's ST).
Lots of people's PhD thesis are in actual use in practical programming today. A PhD thesis often discovers a technique and makes it accessible for real world programs today.
> I don't know of any compiler that actually does a reasonable job converting uses of data structures like lists and association lists into arrays and hash tables in general. I think this falls into the territory of the "sufficiently smart compiler" fallacy.
Converting these is not a good idea because you would change the complexities of the code (which is, IMO, the heart of the fallacy). A prepend of an a-list or a list is O(1), but to a list or hash table, it is (in the worst-case) worse.
But what Haskell's primary compiler, GHC, does do, is fuse together list processing such that lists can disappear altogether into efficient loops.
As for arrays and hash tables, these are not amenable to efficient "pure" modification (unless you use uniqueness types as in Clean), but they have reasonable alternatives that are pure and persistent: Sequence allows O(logN) indexing, O(1) amortized (O(logN) worst-case) prepend/append. Tries and search trees allow for quick lookups and quick pure modification. These are easy to reason about.
> Also, making data contiguous is just the simplest of a common set of data representation optimizations.
This conflicts with O(1) prepend. If you want contiguous allocation, you can use different data structures.
> Does any compiler automatically convert a list into an intrusive doubly linked list or eliminate the use of a visited stack for DFS by stealing a bit from vertices or reversing pointers?
If you need to remove/insert items in the middle of a list, you would probably not use a linked list. So a doubly linked is not a good optimization to apply automatically.
If your point is that code with simpler mathematical semantics that is easy to reason about might cause a constant hit on performance in some cases -- then I agree. You cannot always have simplicity, verifiability, and speed. But often you can.
Also note that purity affords many optimizations that are unavailable in non-pure languages (e.g: rewrite rules like: map f . map g --> map (f . g)).