davidfstr

idris-insertion-sort

Idris2017–2019

davidfstr / idris-insertion-sort

idris-insertion-sort

Provably correct implementation of insertion sort in Idris.

Explore on GitHub Read Hacker News discussions

3Distinct people

5Mentions

0Explicit recommenders

31GitHub stars

REPOSITORY AT A GLANCE

What to know before exploring

What it is

Provably correct implementation of insertion sort in Idris.

GitHub

Where it is used

No documented product use has been verified yet.

What people are saying

No recommendation phrase was found in the indexed comments.

No classified warning is attached to this page. Read the discussions before treating silence as approval.

Also in these discussions

No other repository is repeatedly linked in the same discussions.

This week on Hacker News

Nov 7–Nov 14 UTC · Direct repository links and separately labeled related project stories. Indexed through 11/14/2026, 1:49:46 PM UTC.

No direct repository links were found in the indexed HN discussions over the past seven days. Older discussions are available below.

Mentions over time

HN mentions by month5 dated mentions

Observed mentions: 2017-05-31 12:26:59 UTC to 2019-07-01 12:31:10 UTC.

Counts come from the repository’s dated source evidence. Index cutoff: 2026-11-02 08:16:59 UTC.

View mention counts and date ranges

UTC ranges include their start and exclude their end. Select a period to filter the source evidence.
Period	Start (UTC)	End (exclusive, UTC)	Mentions	Comments
May 2017	2017-05-01 00:00:00 UTC	2017-06-01 00:00:00 UTC	1	1
Jun 2017	2017-06-01 00:00:00 UTC	2017-07-01 00:00:00 UTC	0	0
Jul 2017	2017-07-01 00:00:00 UTC	2017-08-01 00:00:00 UTC	0	0
Aug 2017	2017-08-01 00:00:00 UTC	2017-09-01 00:00:00 UTC	0	0
Sep 2017	2017-09-01 00:00:00 UTC	2017-10-01 00:00:00 UTC	0	0
Oct 2017	2017-10-01 00:00:00 UTC	2017-11-01 00:00:00 UTC	1	1
Nov 2017	2017-11-01 00:00:00 UTC	2017-12-01 00:00:00 UTC	0	0
Dec 2017	2017-12-01 00:00:00 UTC	2018-01-01 00:00:00 UTC	0	0
Jan 2018	2018-01-01 00:00:00 UTC	2018-02-01 00:00:00 UTC	0	0
Feb 2018	2018-02-01 00:00:00 UTC	2018-03-01 00:00:00 UTC	0	0
Mar 2018	2018-03-01 00:00:00 UTC	2018-04-01 00:00:00 UTC	0	0
Apr 2018	2018-04-01 00:00:00 UTC	2018-05-01 00:00:00 UTC	0	0
May 2018	2018-05-01 00:00:00 UTC	2018-06-01 00:00:00 UTC	0	0
Jun 2018	2018-06-01 00:00:00 UTC	2018-07-01 00:00:00 UTC	0	0
Jul 2018	2018-07-01 00:00:00 UTC	2018-08-01 00:00:00 UTC	1	1
Aug 2018	2018-08-01 00:00:00 UTC	2018-09-01 00:00:00 UTC	0	0
Sep 2018	2018-09-01 00:00:00 UTC	2018-10-01 00:00:00 UTC	0	0
Oct 2018	2018-10-01 00:00:00 UTC	2018-11-01 00:00:00 UTC	0	0
Nov 2018	2018-11-01 00:00:00 UTC	2018-12-01 00:00:00 UTC	0	0
Dec 2018	2018-12-01 00:00:00 UTC	2019-01-01 00:00:00 UTC	0	0
Jan 2019	2019-01-01 00:00:00 UTC	2019-02-01 00:00:00 UTC	1	1
Feb 2019	2019-02-01 00:00:00 UTC	2019-03-01 00:00:00 UTC	0	0
Mar 2019	2019-03-01 00:00:00 UTC	2019-04-01 00:00:00 UTC	0	0
Apr 2019	2019-04-01 00:00:00 UTC	2019-05-01 00:00:00 UTC	0	0
May 2019	2019-05-01 00:00:00 UTC	2019-06-01 00:00:00 UTC	0	0
Jun 2019	2019-06-01 00:00:00 UTC	2019-07-01 00:00:00 UTC	0	0
Jul 2019	2019-07-01 00:00:00 UTC	2019-08-01 00:00:00 UTC	1	1

What Hacker News says

5 sources

yogthos·Jul 1, 2019

HM style type inference is nice, but the root problem is that the static type system restricts you to a set of statements that it is able to verify at compile time. This necessarily leads to code that prioritizes the needs of the compiler over those of the human reader. The more things you try to encode using the type system, the more complex your code becomes because proving something correct for all cases is typically significantly more difficult than just stating it and testing for the set of cases you care about. Furthermore, there is no way to verify that your type definitions themselves are correct. When you start moving program logic into types, the compiler cannot help you ensure that it's correct. Here's a fully typed insertion sort [1] written in Idris. It's over 260 lines long, and it takes non trivial amount of effort to under

Read the rest

stand it fully, and know that what it specifies is indeed what was intended. Meanwhile, I can trivially read and understand a 10 line Python version in its entirety. Of course, you could argue that it's an extreme case, and that in practice you probably wouldn't have such an exhaustive type specification. At that point you'd be agreeing that relaxing type constraints does provide a benefit, and we'd just be arguing about our respective levels of comfort. [1] https://github.com/davidfstr/idris-insertion-sort/blob/maste...

In What I Want from a Type System (2016)

yogthos·Jan 13, 2019

Haskell was my first FP language, I used it for about a year, and worked with Scala briefly after. My experience is that you're really trading one set of problems for another in practice. Static typing can guarantee that you avoid a certain class of errors, but it often results in code that's longer and more difficult to understand opening opportunities for different kinds of errors. There is absolutely no empirical evidence to suggest that the trade off is strictly superior in practice. Static typing can catch inconsistencies at the cost of structuring your code in a way that the type checker can understand. This is often at odds with making it readable for the human. A proof only has value as long as the human reader can understand it. Here's a concrete example of what I'm talking about: https://github.com/davidfstr/idris-insertion-sort

Read the rest

/blob/maste... An insertion sort written in Idris has over 250 lines of code that you have to understand to know that it's implemented correctly. A python version would have about 10 lines or less. I'd have much easier time guaranteeing that the 10 lines do exactly what was intended than the 250 lines of type specifications. Of course, you could relax the type guarantees in Idris as well, but at that point you accept that working around the static checker has benefit and it's just a matter of degrees of comfort. In general, the more constraints you specify via types the more of your program logic moves into type specifications. What this really means is that you're writing a metaprogram that emits your logic. However, there's no automated checker for that metaprogram that you wrote using the types. You still have to understand it to be correct in order to know that it's doing what you want it to. At this point you're basically living in a programmer version of the Plato's Cave. The real question is not whether you can do something using a static type system or not. The discussion has to center around how that compares to alternative approaches such as testing, gradual typing, and runtime contracts.

In IBM releases Elm-powered app

yogthos·Jul 2, 2018

Because static typing primarily focuses on showing that your types align. This is completely tangential to knowing that the code is doing what you intended. In fact, it's often at odds with understanding the intent of the code because you're limited to a set of statements that can be verified by the type checker. This can make it harder for the human reader to understand what the code is meant to be doing. For example, it takes nearly 300 lines of code to encode insertion sort using types in Idris https://github.com/davidfstr/idris-insertion-sort/blob/maste... A human reader has to be able to read that and understand that the types are encoding the intent correctly. I don't know about you, but I have a much easier time knowing whether the dynamically typed version in Python is correct or not: def insertionSort(lst): for index

Read the rest

in range(1, len(lst)): currentvalue = lst[index] position = index while position > 0 and lst[position - 1] > currentvalue: lst[position] = lst[position - 1] position = position - 1 lst[position] = currentvalue Complex type definitions effectively become their own meta-programs that the compiler uses to verify your program, but now you've just pushed the problem back a step since somebody still has to read and understand the meta-program to know that it's verifying the correct thing.

In The Machine That Builds Itself: The Strengths of the Lisp Languages (2016)

rbobrowicz·Oct 3, 2017

For someone only passingly familiar with Spec, what's the benefit of Spec over just using a property based testing framework like Haskell's QuickCheck (and I think Clojure's test.check)? I can encode all those invariants as QuickCheck properties and have them automatically tested against random inputs on every test run. It's still all runtime verification, but with random inputs I actually have more confidence of hitting a corner case than with just asserting during regular program runs or hand written example tests. Also, with enough heavy lifting you can actually encode all of that in the types in a dependantly typed language like Idris [1]. And while a machine checked proof of your sorting algorithm is nice, it might be hitting the diminishing returns point the article mentions over just using property tests. [1] https://github.com/dav

Read the rest

idfstr/idris-insertion-sort

In Diminishing returns of static typing

infinisil·May 31, 2017

That's where formal proofs come into play, because you need to somehow show that the implementation actually does what the definition states. Since Haskell isn't a proof checker you can't use it for this. The newish and very promising looking language Idris [1], which is very similar to Haskell, can actually do this because of having dependent types. Upon a quick search I found this great example [2] of a proof that insertion sort does indeed return the list sorted, all in the type system. I can really recommend Type Driven Development [3], a recently released book on development in Idris. [1]: https://www.idris-lang.org/ [2]: https://github.com/davidfstr/idris-insertion-sort [3]: https://www.manning.com/books/type-driven-development-with-i...

In Imperative Haskell