Haskell Study Note 01, Sorting
This article is about implementing the four basic sorting algorithms in Haskell: bubble & insert & quick & merge.
Hope myself can keep sharing things I experienced from the journey of learning Haskell on a weekly basis :)
Why Haskell?
- I want to understand Cardano’s codebase.
- It’s about 6 years since I started programming with C/C#/JavaScript, it’s good to learn a purely functional language to broaden the mindset.
- Features like strong type and tools like QuickCheck are very appealing to me.
Get Started
While waiting for amazon’s package for the book Real World Haskell, I learned a lot from Learn You a Haskell for Great Good!, it’s a beginner friendly guide.
As many other programming guides, “for Great Good” includes the environment set-up guide and how-to “Hello World”, so I won’t include these two parts in this article 😛
Insert Sort
You can try it out directly on REPL:
Line 1 defines the type of insertSort:
giving that a’s type is an instance of Ord type class, when the input of insertSort is an array of a, the output will also be an array of a.
For example, giving the function a number array will yield another number array.
Line 2 and line 3 leverage the pattern matching feature, [] is for handling empty array and (a:b) can separate non-empty array into two parts.
To insert sorting, we need to create an array to hold the sorting result, recursively insert more elements into that array, returns the result. Line 3 does that.
Line 4 defines the insert and limiting its scope inside insertSort by using where.
Apart from pattern matching, we can also use guard to assign different handlers for different types of inputs, which is being used in the insert function.
So, that’s the insert sort, I’ll just copy-paste my solutions for other sorting algorithms below :)
Since I’m new to Haskell, there must be some stupid mistakes or bad patterns, please tell me if you noticed some!
Bubble Sort
As you may notice, there are different ways to construct arrays in Haskell, the a:a:a:…:[a] in the insertSort, and the [a]++[a] being used here.
Merge Sort
Quick Sort
That’s it :)
My next Haskell study note will be about the Modules (know nothing about how it works in Haskell right now).
Apart from that, I also listed something below which are some nice to be learned as soon as possible 😃
To-learn List
- How to test code with QuickCheck?
- How to test the performance of Haskell code, benchmark the performance?
