Haskell Notes

I wanted to learn more about Haskell so I can understand the Pandoc code base more.

• Resource Used For This Note
  • Suggested Resources to Learn Haskell
    • A Gentle Introduction to Haskell
    • Learn You a Haskell for Great Good!
    • The Haskell School of Expression
    • Haskell Wiki Page on Functional Programming

This is an online course on Functional Programming that uses the Haskell programming language. This course is aimed at beginners who wish to learn functional programming, but also people who have experience with functional programming and want to learn Haskell in particular. The course assumes no previous knowledge.

Haskell

Haskell is:

• functional: the basic building blocks of programs are functions. Functions can return functions and take functions as arguments.
• pure: Haskell functions are pure, they don't have side effects. Side effects mean things like reading a file, printing out text, or changing global variables. All inputs to a function must be its arguments, and all outputs from a function in its return value.
• lazy: values are only evaluated when they are needed
• strongly typed: every Haskell expression has a type. The compiler checks the types at compile-time and guarantees that no type errors can happen at runtime.
• type inferred: in addition to checking the types, the compiler can deduce the types for most programs. This makes working with a strongly typed language easier.
• garbage collected: Haskell has most automatic memory management via garbage collection
• compiled: Haskell programs can be compiled to very efficient binaries, and the GHC compiler is very good at optimizing functional code into performant machine code.

Features

• Higher-order functions: functions can take functions as arguments
• Anonymous functions aka lambdas: you can define single-use helper functions without giving them a name
• Partial application: you can define new functions by giving another function only some of the arguments it needs.
• Algebraic datatypes: a syntax for defining datatypes that can contain a number of different cases
• Pattern matching: defining functions based on cases that correspond to your data definitions
• Lists: Unlike many languages, Haskell has a concise built-in syntax for lists.
• Parameterized Types: you can define types that are parameterized by other types
• Type classes: another form of polymorphism where you can give a function a different implementation depending on the arguments' types

Haskell Uses

• The Pandoc tool for converting between different document formats
• The PostgREST server that exposes a HTTP REST APU for a PostgreSQL database

Running Haskell

The easiest way to get Haskell is to install the stack tool, see this resource for instructions. Type stack ghci in the command line to start using Haskell. Prelude> is the GHCi prompt. It indicates that we can use the functions from the Haskell base library called Prelude. The :type GHCi command can give you the type of an expression. The tail function works on lists and returns all except the first element of the list.

Expressions and Types

expressions and types are the bread and butter of Haskell. In fact, almost everything in a Haskell program is an expression. There are no statements like in Python, Java, or C. An expression has a value and a type. We write an expression and its type like this: expression :: type.

Syntax of Expressions

Expressions consist of functions applied to arguments. Functions are applied (called) by placing the arguments after the name of the function - there is no special syntax for a function call.

Parentheses can be used to group expressions (just like in math or other languages).

Function calls bind tighter than operators, just like multiplication binds tighter than addition. Function application associates left.

Syntax of Types

Some basic types of Haskell to get you started.

The names of types in Haskell start with a capital letter. Some values like True also start with a capital letter, but variables and functions start with a lower case letter (reverse, not, x). Functions are written using the -> syntax:

• A function with one argument: argumentType -> returnType
• 2 args: argument1Type -> argument2Type -> returnType
• 3 args: argument1Type -> argument2Type -> argument3Type -> returnType

In Haskell, number literals are overloaded which means they can be interpreted as any number type (e.g. Int or Double). The type String is just an alias for type [Char] which means "list of characters".

The Structure of a Haskell Program

Haskell uses the .hs file extension, and you can run a haskell file with stack runhaskell <filename>.

• module Gold where: There is one Haskell module per source file. A module consists of definitions
• -- the golden ratio: This is a comment. Comments are not actual parts of the program
• phi :: Double: Definition of teh constant phi, with an accompanying type annotation (also known as a type signature). The type annotation means that phi has type Double
• phi = (sqrt 5 + 1) / 2: This line is called an equation. The left hand side of the = is the expression we are defining, and the right hand side of the = is the definition.
• In general, a definition (or a function or constant) consists of an optional type annotation and one or more equations

polynomial :: Double -> Double
polynomial x = x^2 - x - 1

The above is a definition of a function called polynomial. It has a type annotation and an equation. Note how an equation for a function differs from the equation of a constant by the presence of a parameter x left of the = sign. Note that ^ is the power operator in Haskell. The code below is the definition of a function called f.

f x = polynomial (polynomial x)

The below code is the description of what happens when you run the program. It uses do-syntax and the IO Monad. You can use ; to separate lines or use the special :{:} syntax to paste a block of code into GHCi. You can :load code form a file into the GHCi. If the file has already been loaded, you can use reload.

How do I get anything Done?

Conditionals

In other languages, if is a statement. It doesn't have a value, it just conditionally executes other statements. In Haskell, if is an expression. It has a value. It selects between two other expressions. It corresponds to the ?: operator in C or Java.

price = if product == "milk" then 1 else 2

Because Haskell's if returns a value, you always need an else. The not-equals operator is written /= in Haskell.

Haskell has two different ways of creating local definitions: let ... in and where. where adds local definitions to a definition:

circleArea :: Double -> Double
circleArea r = pi * rsquare
    where pi = 3.1415926
          rsquare = r * r

let... in is an expression:

circleArea r = let pi = 3.1415926
                   rsquare = r * r
               in pi * rsquare

Haskell variables into which you can put new values. Haskell variables name a value (or rather, an expression) and that's it.

A defintion of a function can consist of multiple equations. The equations are matched in order against the arguments until a suitable one is found. This is called pattern matching. Pattern matching in Haskell is very powerful:

greet :: String -> String -> String
greet "Finland" name = "Hei, " ++ name
greet "Italy"   name = "Ciao, " ++ name
greet "England" name = "How do you do, " ++ name
greet _         name = "Hello, " ++ name

The function greet generates a greeting given a country and a name (both Strings). It has a special case for three casesm and then a default case. The special pattern _ matches anything. it's usually used for default cases. The standard library function show can turn almost anything into a string.

In Haskell, all sorts of loops are implemented with recursion. Function calls are very efficient, so you don’t need to worry about performance.

In Haskell indentation matters, a bit like in Python. The complete set of rules for indentation is hard to describe, but you should get along fine with these rules of thumb:

1. Things that are groped together start from the same column.
2. If an expression (or equation) has to be split on to many lines, increase indentation.

Haskell helper variables for recursive functions:

repeatString n str = repeatHelper n str ""

repeatHelper 0 _   result = result
repeatHelper n str result = repeatHelper (n-1) str (result++str)

Haskell's conditional definition or guarded definition is a better way to handle conditionals with multiple cases. This is a bit like pattern matching in that you have multiple equations, but you can have arbitrary code deciding which equation to use.

describe :: Int -> String
describe n
  | n==2      = "Two"
  | even n    = "Even"
  | n==3      = "Three"
  | n>100     = "Big!!"
  | otherwise = "The number "++show n

The basic data structure in Haskell is the list. Lists are used to store multiple values of the same type (Haskell lists are homogenous). Haskell lists are implemented as singly linked lists.

[True,True,False] :: [Bool]
["Moi","Hei"] :: [String]
[] :: [a]                   -- more about this later
[[1,2],[3,4]] :: [[Int]]    -- a list of lists
[1..7] :: [Int]             -- range syntax, value [1,2,3,4,5,6,7]

The Haskell standard library comes with a lot of functions that operate on lists. here are some of the most important ones, together with their types:

head :: [a] -> a            -- returns the first element
last :: [a] -> a            -- returns the last element
tail :: [a] -> [a]          -- returns everything except the first element
init :: [a] -> [a]          -- returns everything except the last element
take :: Int -> [a] -> [a]   -- returns the n first elements
drop :: Int -> [a] -> [a]   -- returns everything except the n first elements
(++) :: [a] -> [a] -> [a]   -- lists are catenated with the ++ operator
(!!) :: [a] -> Int -> a     -- lists are indexed with the !! operator
reverse :: [a] -> [a]       -- reverse a list
null :: [a] -> Bool         -- is this list empty?
length :: [a] -> Int        -- the length of a list

Some list operations come from the module Data.List. You can import a module in code or in GHCi with the import Data.List syntax. One example is the sort function which sorts a list:

Prelude> import Data.List
Prelude Data.List> sort [1,0,5,3]
[0,1,3,5]

Because Haskell is pure, it also means that functions can't mutate (change) their inputs. Mutation is a side effect, and Haskell functions are only allowed output via their return value. This means that Haskell list functions always return a new list.

So what does a type like head :: [a] -> a mean? It means given a list that contains elements of any type a, the return value will be of the same type a. a is a type variable. A type variable means a type that is not yet known, or in other words a type that could be anything. Two variables can turn into concrete types by the process of type inference.

In a type like [Char] we call Char a type parameter. A type like the list type that needs a type parameter is called a parameterized type.

<meta property="og:type" content="article" />
<meta property="og:type" content="any string" />
<meta property="og:image" content="valid image url" />
<meta property="og:description" content="any string" />

#include <stdio.h>

void bubble_sort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n-1; i++) {
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}