The RunLength data type is built such as if you give it a list, it gives you a (unique) type.
And the only two constructors available are such that they enforce the encoding.
Try to unroll an example or build one from the definition and you’ll get it eg.:
How would you build an element of this type?
RunLength [1 1 1 3 3 7 7 7]The input parameters to the "functions" appear to be data elements from within the compressed list. Because that's what they are. But this wasn't obvious to me.
I think the weird bit is when the tags and fields within a datatype are represented using the same syntax as a function's name and parameters. This punning threw me off. I suppose the same is true in Haskell, but you don't write type constructors using '->' between the fields, so this punning is less obvious. (And Haskell's syntax for product types is itself less familiar to me than a 'struct' definition in a C-like language.)
That's exactly how you write GADTs in Haskell: https://downloads.haskell.org/~ghc/6.6/docs/html/users_guide....
> how the data is stored
Thinking of how concretely the data is stored is a little bit tricky. I find it easier to build an intuition by looking at what kind of values the type signature lets us build, and which values are disallowed.
runLengthOfAnEmptyList : RunLength []
runLengthOfAnEmptyList = Empty
-- Note that 1 is shorthand for (S Z)
runLengthOfAListWithOneElement : RunLength [ 1 ]
runLengthOfAListWithOneElement = Run 0 1 Empty
-- The definition of RunLength places restrictions on how to
-- construct it.
-- For example, this will not compile.
runLengthOfAListWithOneElementBrokenVersion : RunLength [ 1 ]
runLengthOfAListWithOneElementBrokenVersion = Run 1 1 Empty
--
-- This violates the type signature of RunLength
-- Notice Run 1 1 Empty which has changed the 0 to a 1
--
-- As a reminder this is the definition of Run
-- Run : ( n : Nat ) -> ( x : ty ) -> ( rle : RunLength more ) ->
-- RunLength ( rep ( S n ) x ++ more )
--
-- n is set to 1, x is set to 1, and Empty means that more is set to []
-- Making the necessary substitutions results in:
-- RunLength ( rep ( S n ) x ++ more ) -- No substitutions yet
-- RunLength ( rep ( S 1 ) 1 ++ [] ) -- S 1 is the same thing as S (S Z)
-- RunLength ( 1 :: 1 :: [] ++ [] ) -- Substituting rep ( S 1 ) 1
-- RunLength ( 1 :: 1 :: [] ) -- ++ [] doesn't change our list at all
-- RunLength [ 1, 1 ] -- Syntax sugar for 1 :: 1 :: []
--
-- But this is a contradiction! Since we said in our type annotation that we
-- should have RunLength [ 1 ], not RunLength [ 1, 1 ]!
However I agree with you that this style of dependently typed programming is confusing and ultimately in my view, a bad representation of how dependent types should be used in production code (if any full-spectrum dependently typed language gains enough adoption to be used in large production projects).Here's the same idea in an alternative, but (roughly) equivalent, encoding, which hopefully lays it out more clearly.
RuntimeEncodedList : Type -> Type
RuntimeEncodedList t = List (Nat, t)
uncompress : RuntimeEncodedList t -> List t
uncompress runtimeEncodedList = case runtimeEncodedList of
[] => []
(n, elem) :: restOfList => rep (n + 1) elem ++ uncompress restOfList
compress : List t -> RuntimeEncodedList t
compress = ...
uncompressIsTheInverseOfCompress :
uncompress (compress xs) = xs
uncompressCorrectlyUncompressesEmptyLists = ...
I hope this is a much plainer and easier to understand representation, with a similarly strong invariant. The `...` are of course eliding a lot, but my point is that they can be elided, without really affecting comprehension of the overall code (which is not the case with the other representation).This also nicely avoids a problem I see in a lot of dependently code where the structural representation of data structures are intertwined with the invariants they are supposed to uphold. Not only does this result in increasingly confusing code as the invariants get more sophisticated and also awkwardly privileges certain invariants over others, it makes modifying the representation in even the smallest ways a nightmarish test of resolve. This is because everywhere you want to create the data structure, you must also prove that the invariants hold. Sometimes this proof is trivial, sometimes this proof is difficult. But you must always do this, you cannot bail out with some sort of "believe me" escape hatch where you maybe use some sort of external solver to prove it instead, because you can now potentially crash or even segfault your program, even if your code would otherwise fulfill the invariant through some other reasoning the compiler cannot see, since the proof is an integral part of the runtime representation of the data structure.
This sort of proof burden means that it can be a Herculean task to swap out the underlying representation of the data structure for a more efficient one (e.g. you're going to be in for a hard time if you've written code with the `RunLength` type and all of a sudden, for speed reasons, you'd prefer an underlying representation of run length encoded types that groups all the run lengths in one array and stores all the actual values in another array). At least having zero multiplicity annotations on parts of the dependently typed data structure makes things a bit easier.
I instead advocate for a clean separation where the overwhelming majority of data types in a dependently-typed program should be non-dependently-typed and dependent types used instead merely to state properties about those data types independently.
I suppose laziness makes it somewhat more practical. The concrete type may only exist conceptually.
It's also unclear what constraint is being enforced. Proving that all run-length encodings decompress to some list doesn't seem interesting? This is just as true of your encoding. I suppose it would be more interesting if not every possible value of the compressed data structure were valid, such as if it contained a cached checksum that needed to match the data. We could show that all compress functions compute the checksum correctly.
But couldn't do that by having a single compress function and proving that it works? Why have more than one?
Also, it seems like verifying such a checksum would be weird. In the presence of data corruption, you would have a proof that that checksum matches the data, but by computing the checksum you could show that it doesn't match the data.
Apparently type-checking proofs aren't really about concretely showing that data is consistent? If you rely on the proof, you assume correct data rather than verifying it. A sufficiently smart compiler might optimize away your attempted verification?
I agree it's a bit tricky to understand (which is why I don't like that representation), but this has nothing to do with laziness (Idris is a strict language). It's a more general phenomenon that values in a type signature do not actually have to exist at runtime. It's purely a notational thing that lives in the type-checkers "brain" and has no runtime representation. At runtime, `compress` really does compress the list without keeping a copy of it anywhere. For any type `MyType someValue`, there's no a priori reason `someValue` should actually have any runtime representation. See e.g.
data MyType : Int -> Type
TheOnlyThingOfMyType : MyType 5
-- There's no way to actually access the 5 at runtime
-- It only lives in type signatures
someValue : MyType 5
someValue = TheOnlyThingOfMyType
-- This addition takes place at compile time, not runtime
someOtherValue : MyType (4 + 1)
someOtherValue = TheOnlyThingOfMyType
thisFailsToCompile : MyType (4 + 2)
thisFailsToCompile = TheOnlyThingOfMyType
There is likewise no reason to believe something like `SomeOtherType String` actually has a string in it anywhere (this pattern is known as a phantom type) without knowing more about `SomeOtherType`. All the type parameter does is constrain how functions can be called that involve the overall type. In this sense `List String` having an actual `String` you can pull out of it at runtime can be thought of as the exception rather than the norm (and indeed isn't always the case, e.g. if you have an empty list).In this case, you can use `RunLength`'s list parameter to state more invariants, even if the list doesn't exist at runtime.
-- If two lists compress to the same thing, then they must've been the same to begin with
compressionIsLossless : RunLength xs = RunLength ys -> xs = ys
-- Here follows the proof of that statement
-- If the proof looks confusing, https://shuangrimu.com/posts/language-agnostic-intro-to-dependent-types.html might help
compressionIsLossless runLengthsAreEqual = case runLengthsAreEqual of
Refl => Refl
Switching back to my representation...> But couldn't do that by having a single compress function and proving that it works? Why have more than one?
I only have one compress function (I was just too lazy to write it out and used ellipses instead).
> Proving that all run-length encodings decompress to some list doesn't seem interesting? This is just as true of your encoding.
The constraint is fairly simple, but very strong (although I made a typo where the name associated with the type signature and the actual implementation's name are different, d'oh):
uncompressIsTheInverseOfCompress : uncompress(compress xs) = xs
uncompressIsTheInverseOfCompress = ... -- Too lazy to write out the actual proof at the moment
This is the fundamental property all lossless compression schemes must satisfy.You could also of course add all sorts of other properties.
-- Even though it won't inflate list length, it can result in more memory usage due to the tuples
compressWontInflateSize : (length (compress xs) <= length xs) = True
compressWontInflateSize = ... -- Again too lazy to write out the proof
-- Idris doesn't have a general exists statement so we need to provide a
-- concrete example
compressMakesAtLeastOneListSmaller : (length (compress [1, 1, 1]) <= length [1, 1, 1])) = True
compressMakesAtLeastOneListSmaller = Refl
-- This proof is easy, just tell Idris to actually do the calculation (at compile-time, not run-time!)
> Apparently type-checking proofs aren't really about concretely showing that data is consistent? If you rely on the proof, you assume correct data rather than verifying it. A sufficiently smart compiler might optimize away your attempted verification?I'm not sure what you mean here. In order to show that your data is consistent you need to describe what you mean by consistency somehow. You can do that either within the definition of a type itself (which I do not like) or you can do that by explaining how different functions are supposed to relate to each other (e.g. how compress, uncompress, and length should be related to each other), which I like more.
As for "optimizing away verification," that's the point of Idris' 0 multiplicity. It marks something as "compile-time-only" that has no runtime representation and hence no runtime performance impact.
The definition of `RuntimeLength` does not do away with the need to define `uncompress`, all it does is move it into the definition of `RuntimeLength`. In fact my version of `RuntimeEncodedList` and `uncompress` is less overall code than `RuntimeLength` and `uncompress`. Indeed the only reason the compiler can synthesize `uncompress` is because it duplicates `RuntimeLength`! So really the compiler hasn't reduced the amount of work that needs to be done. Just like I could've messed up my definition of `uncompress`, its equivalent in `RuntimeLength` could also have been written incorrectly. We haven't reduced the amount of code that needs to be checked by a human for correctness (in the absence of other invariants), only moved it from a function definition to a data type definition.
By moving it into a function, however, we can then selectively add as many additional properties as we want (such as the `uncompress(compress xs) == xs` invariant), without having to worry about privileging one over any other.
Instead of
append : Vector n a -> Vector m a -> Vector (n + m) a
I'd prefer just append : List a -> List a -> List a
and a separate theorem appendSumsLength : (xs : List a) -> (ys : List a) -> length (append xs ys) = length xs + length ys
Sure it's wordier in the short-term, but I think it pays dividends in longer term maintenance.To be clear though this is a minority position. Other programmers will argue that putting the size parameter in the data type itself makes a lot of proofs essentially trivial and that at least in the case of sized vectors, the issue of "privileging a single invariant" is less of an issue, because the only defining feature of a polymorphic list is its length. I personally disagree with the merits of this trade-off for most production code, but that's starting to get into the weeds.
In the run length encoding example, I don’t understand how the runtime data structure is defined. There is a Runlength data type, but its definition looks more like a Haskell-style curried function definition than a data definition. It seems to call the ‘rep’ function and the list concatenation operator, but how do you get a datatype out of that? If you drew a boxes and arrows diagram showing how the data is stored, what would it look like?
I’m wondering if this is like how you can use a closure to store data in captured local variables? Or perhaps like lazy evaluation in Haskell?