Functional programming L+Pr

DarthDemono’s Notes for Functional programming L+Pr / IP-18fFUNPEG

This course attempts to teach a completely different form of programming compared to what we

Course code: IP-18fFUNPEG
Credits: 6

Setup (what you install + what you run)

You’ll use GHC (the Haskell compiler) and usually run files either by interpreting them or compiling them.

1) Install GHC using GHCup (proper tutorial)

GHCup is the standard toolchain manager for Haskell: it can install and manage GHC, cabal, and optionally stack/HLS.

You can follow the official guidelines

A) Windows (native)

Create a folder where GHCup will live (pick a drive with space), e.g.:
- C:\ghcup\bin

Run this PowerShell script

Set-ExecutionPolicy Bypass -Scope Process -Force;[System.Net.ServicePointManager]::SecurityProtocol = [System.Net.ServicePointManager]::SecurityProtocol -bor 3072; try { & ([ScriptBlock]::Create((Invoke-WebRequest https://www.haskell.org/ghcup/sh/bootstrap-haskell.ps1 -UseBasicParsing))) -Interactive -DisableCurl } catch { Write-Error $_ }

Open a terminal and run the basic installs (recommended flow from the official instructions):
- Install a recommended GHC and set it active:
```
ghcup install ghc
```
- Install cabal:
```
ghcup install cabal latest
```
- (Optional) install stack:
```
ghcup install stack latest
```
- (Optional) install Haskell Language Server:
```
ghcup install hls latest
```

B) Linux / macOS (and WSL)

Run the official bootstrap script (interactive installer):

curl --proto '=https' --tlsv1.2 -sSf https://get-ghcup.haskell.org | sh

The installer may offer to update your shell PATH automatically; accept if you want it to “just work” in new terminals.
Open a new terminal window (or reload your shell config) so your PATH changes take effect.

C) Verify everything works (all platforms)

Run:

ghc --version
runghc --version
cabal --version If these commands return proper versions, the toolchain is installed correctly.

D) Quick sanity test (hello world)

Create Main.hs:

main :: IO ()
main = putStrLn "Hello Haskell"

Run it:

runghc Main.hs

If it prints Hello Haskell, you’re ready for labs.

Syllabus (what you actually learn)

Topics you need to learn:

Defining functions, guards, recursion, elementary types
Syntax, reduction steps, normal form, lazy vs eager evaluation
Standard functions, predefined operators
Data structures: lists, tuples, records, arrays
List processing: definitions, generators, patterns, recursion
Types: simple, algebraic, composite, trees
Algorithms: search, sort, traverse
Higher-order functions: map, filter, iterate, fold
Tuples, list comprehensions, equivalences
Sorting, merging
Infinite lists
Algebraic types, trees, ADTs
Recursions

What to target

List Comprehension: once List Comprehension clicks, half the course becomes easier.
Recursion

Haskell Learning Resources

These resources from the Functional Programming syllabus provide curated materials for Haskell study, ranging from beginner guides to advanced topics.

Beginner Tutorials

Discourse: Best Haskell Materials 2024 – Community-curated top resources.
Haskell Books Index – 77+ books tagged by level and topic.
code.world (9 resources) & code.world/haskell (29 hands-on sites).
Haskell Wiki & Wikibooks Haskell – Core references (not identical).

Research & Guides

Haskell Learning Guide

List Operations

Sort high to low

import Data.List (sortOn)
import Data.Ord  (Down(..))
 
sortDown :: [Int] -> [Int]
sortDown xs = sortOn Down xs
 
main = print (sortDown [2,3,4,6])
-- [6,4,3,2]

Sort low to high

import Data.List (sort)
 
sortUp :: [Int] -> [Int]
sortUp xs = sort xs
 
main = print (sortUp [2,3,4,6])
-- [2,3,4,6]

Return odd indices (1,3,5…)

oddIndices :: [a] -> [a]
oddIndices xs = [ x | (i, x) <- zip [0..] xs, odd i ]
 
main = print (oddIndices [2,3,4,6])
-- [3,6]

Return even indices (0,2,4…)

evenIndices :: [a] -> [a]
evenIndices xs = [ x | (i, x) <- zip [0..] xs, even i ]
 
main = print (evenIndices [2,3,4,6])
-- [2,4]

Adjacent pairs (overlapping)

adjacentPairs :: [a] -> [(a,a)]
adjacentPairs xs = zip xs (tail xs)
 
main = print (adjacentPairs [2,3,4,6])
-- [(2,3),(3,4),(4,6)]

Non-overlapping pairs

pairs2 :: [a] -> [(a,a)]
pairs2 (x:y:rest) = (x,y) : pairs2 rest
pairs2 _          = []
 
main = print (pairs2 [2,3,4,6])
-- [(2,3),(4,6)]

All prefixes

allPrefixes :: [a] -> [[a]]
allPrefixes xs = [ take i xs | i <- [1 .. length xs] ]
 
main = print (allPrefixes [2,3,4,6])
-- [[2],[2,3],[2,3,4],[2,3,4,6]]

Int to List

import Data.Char (digitToInt)
 
intToDigits :: Int -> [Int]
intToDigits n = map digitToInt (show (abs n))
 
main = print (intToDigits 1234)
-- [1,2,3,4]

List Comprehensions

Filter with condition

filterDivisible :: [(Int,Int)] -> [(Int,Int)]
filterDivisible pairs =
  [ (a,b) | (a,b) <- pairs, a `rem` b == 0 ]
 
main = print (filterDivisible [(6,3),(4,2),(5,2)])
-- [(6,3),(4,2)]

Multiple generators + guards

multiGen :: [Int] -> [(Int,Int)]
multiGen ys =
  [ (a,b)
  | (i,a) <- zip [0..] ys
  , (j,b) <- zip [0..] ys
  , i < j
  , a `rem` b == 0
  ]
 
main = print (multiGen [2,3,4,6])
-- [(4,2),(6,2),(6,3)]

Cartesian product

cartesian :: [Int] -> [Int] -> [(Int,Int)]
cartesian xs ys = [ (x,y) | x <- xs, y <- ys ]
 
main = print (cartesian [1..3] [4..6])
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Higher-Order Functions

Map with index

mapWithIndex :: (Int -> a -> b) -> [a] -> [b]
mapWithIndex f xs = [ f i x | (i,x) <- zip [0..] xs ]
 
main = print (mapWithIndex (+) [10,20,30])
-- [10,21,32]

Filter then map (selectiveMap)

selectiveMap :: (a -> Bool) -> (a -> a) -> [a] -> [a]
selectiveMap p f xs = [ if p x then f x else x | x <- xs ]
 
main = print (selectiveMap even (*2) [1,2,3,4])
-- [1,4,3,8]

Common Patterns

Attach indices

attachIndices :: [a] -> [(Int,a)]
attachIndices xs = zip [0..] xs
 
main = print (attachIndices [2,3,4,6])
-- [(0,2),(1,3),(2,4),(3,6)]

All unique pairs (i < j)

uniquePairs :: [a] -> [(a,a)]
uniquePairs ys =
  [ (a,b)
  | (i,a) <- zip [0..] ys
  , (j,b) <- zip [0..] ys
  , i < j
  ]
 
main = print (uniquePairs [2,3,4])
-- [(2,3),(2,4),(3,4)]

Divisible pairs

import Data.List (sortOn)
import Data.Ord  (Down(..))
 
divisiblePairs :: [Int] -> [(Int,Int)]
divisiblePairs xs =
  [ (a,b)
  | (i,a) <- zip [0..] ys
  , (j,b) <- zip [0..] ys
  , i < j
  , a `rem` b == 0
  ]
  where ys = sortOn Down xs
 
main = print (divisiblePairs [2,3,4,6])
-- [(6,3),(6,2),(4,2)]

Matrix sum of squared differences

ssd :: [[Int]] -> [[Int]] -> Int
ssd xs ys =
  sum [ (a-b)^2
      | (rowX,rowY) <- zip xs ys
      , (a,b) <- zip rowX rowY
      ]
 
main = print (ssd [[1,2],[3,4]] [[2,2],[1,5]])
-- 6

Midterm / Endterm Patterns

Count odd digits

countOdds :: Int -> Int
countOdds n = length $ filter odd digits
  where digits = map (read . (:[])) (show (abs n))
 
main = print (countOdds 135246)
-- 3

Common elements (unique)

import Data.List (nub)
 
commonElements :: Eq a => [a] -> [a] -> [a]
commonElements xs ys = nub [ x | x <- xs, x `elem` ys ]
 
main = print (commonElements [1,2,2,3,4] [2,4,4,5])
-- [2,4]

Remove numbers divisible by 5

removeDiv5 :: [Int] -> [Int]
removeDiv5 = filter (\x -> x `mod` 5 /= 0)
 
main = print (removeDiv5 [5,10,12,15,17])
-- [12,17]

Arithmetic sequence

arithmeticSequence :: Int -> Int -> Int -> [Int]
arithmeticSequence a d n = take n $ iterate (+d) a
 
main = print (arithmeticSequence 2 3 5)
-- [2,5,8,11,14]

Count vowels (case-insensitive)

countVowels :: String -> Int
countVowels = length . filter (`elem` "aeiouAEIOU")
 
main = print (countVowels "Education")
-- 5

Prime check

isPrime :: Int -> Bool
isPrime x = divisors x == [1,x]
  where
    divisors n    = filter (`divides` n) [1..n]
    divides d n   = n `rem` d == 0
 
main = print (isPrime 29)
-- True

Replace with occurrence count

replaceWithOccurrence :: [Int] -> [Int]
replaceWithOccurrence xs = map (\x -> count x xs) xs
  where count y = length . filter (== y)
 
main = print (replaceWithOccurrence [1,2,2,3])
-- [1,2,2,1]

Decimal to Binary

toBinary :: Int -> String
toBinary 0 = "0"
toBinary k = reverse (helper k)
  where
    helper 0 = []
    helper y =
      let (q,r) = y `divMod` 2
      in (if r == 0 then '0' else '1') : helper q
 
main = print (toBinary 13)
-- "1101"

Perfect numbers

perfectNumbers :: Int -> [Int]
perfectNumbers n =
  [ x | x <- [2..n]
      , sum (init (divisors x)) == x
      ]
  where
    divisors k = [ d | d <- [1..k], k `rem` d == 0 ]
 
main = print (perfectNumbers 500)
-- [6,28,496]

Student averages

import Data.List (genericLength)
 
averageScores :: [(String,[Double])] -> [(String,Double)]
averageScores =
  map (\(name,scores) -> (name, sum scores / genericLength scores))
 
main = print (averageScores [("Alice",[80,90]),("Bob",[70,85,75])])
-- [("Alice",85.0),("Bob",76.66666666666667)]

Numeric helpers

Dot product of two lists

dotProd :: [Int] -> [Int] -> Int
dotProd xs ys = sum [ x * y | (x,y) <- zip xs ys ]
 
main = print (dotProd [1,2,3] [4,5,6])
-- 32

Average of a list (generic numeric)

avg :: (Real a, Fractional b) => [a] -> b
avg xs = realToFrac (sum xs) / fromIntegral (length xs)
 
main = print (avg [1,2,3,4] :: Double)
-- 2.5

Parallel list comprehensions

Elementwise `v1 + v2 * v3`

{-### LANGUAGE ParallelListComp #-}
 
mulAddA :: [Int] -> [Int] -> [Int] -> [Int]
mulAddA v1 v2 v3 = [ a + b * c | a <- v1 | b <- v2 | c <- v3 ]
 
main = print (mulAddA [1,2] [3,4] [5,6])
-- [16,26]

Elementwise product and safe division

{-### LANGUAGE ParallelListComp #-}
 
elementWise :: [Double] -> [Double] -> ([Double],[Double])
elementWise xs ys = (products, divisions)
  where
    products  = [ x * y           | x <- xs | y <- ys ]
    divisions = [ if y == 0 then 0 else x / y
                | x <- xs | y <- ys ]
 
main = print (elementWise [4,6] [2,0])
-- ([8.0,0.0],[2.0,0.0])

Tuples and Booleans

Combine tuples with `Int` and `Bool`

processTuples :: [(Int,Bool)] -> [(Int,Bool)] -> Int
processTuples xs ys =
  sum [ if b1 && b2 then a1 + a2 else a1 - a2
      | (a1,b1) <- xs
      | (a2,b2) <- ys ]
 
main = print (processTuples [(5,True),(3,False)] [(2,True),(1,True)])
-- 5

Records and updates

data Univ = Univ
  { uniName :: String
  , uniID   :: Int
  } deriving (Show,Eq)
 
data Student = Student
  { neptunID    :: Int
  , studentName :: String
  , uni         :: Univ
  , grades      :: [Int]
  } deriving Show

Rename a university (by `uniID`)

renameUniversity :: Univ -> String -> [Student] -> [Student]
renameUniversity target newName =
  map (\s ->
    if uniID (uni s) == uniID target
    then s { uni = (uni s) { uniName = newName } }
    else s)
 
main =
  let u1 = Univ "ELTE" 1
      u2 = Univ "BME"  2
      sts =
        [ Student 1 "Alice" u1 [90,95]
        , Student 2 "Bob"   u2 [70,80]
        ]
  in print (renameUniversity u1 "ELTE Budapest" sts)

Outstanding students (>90)

outstandingStudents :: [Student] -> [String]
outstandingStudents sts =
  [ studentName s | s <- sts, any (>90) (grades s) ]
 
main =
  let u = Univ "ELTE" 1
      sts =
        [ Student 1 "Alice" u [88,92]
        , Student 2 "Bob"   u [70,80]
        ]
  in print (outstandingStudents sts)
-- ["Alice"]

Trees

Binary tree and subtree swap

data Tree a = Node a (Tree a) (Tree a) | Leaf
  deriving Show
 
swapSubTree :: Tree a -> Tree a
swapSubTree Leaf         = Leaf
swapSubTree (Node x l r) = Node x (swapSubTree r) (swapSubTree l)
 
main =
  let t = Node 1 (Node 2 Leaf Leaf) (Node 3 Leaf Leaf)
  in print (swapSubTree t)
-- Node 1 (Node 3 Leaf Leaf) (Node 2 Leaf Leaf)

Expression trees to infix string

data ExpressionTree a
  = Operand a
  | Operator String (ExpressionTree a) (ExpressionTree a)
  deriving Show
 
evaluate :: ExpressionTree String -> String
evaluate (Operand x)        = x
evaluate (Operator op l r)  =
  "(" ++ evaluate l ++ op ++ evaluate r ++ ")"
 
main =
  let expr = Operator "+"
              (Operand "3")
              (Operator "*" (Operand "4") (Operand "5"))
  in print (evaluate expr)
-- "(3+(4*5))"

Algebraic data types and pattern matching

data Color = Red | Blue | Yellow | Purple | Orange | Green
  deriving (Show,Eq)
 
combineColors :: Color -> Color -> Color
combineColors Red   Blue   = Purple
combineColors Blue  Red    = Purple
combineColors Red   Yellow = Orange
combineColors Yellow Red   = Orange
combineColors Blue  Yellow = Green
combineColors Yellow Blue  = Green
combineColors c1    c2
  | c1 == c2  = c1
  | otherwise = error "Unsupported combo"
 
main = print (combineColors Red Blue)
-- Purple

Type Class Instances

data Team = Team
  { teamName :: String
  , teamID   :: Int
  }
 
data Player = Player
  { playerID     :: Int
  , playerName   :: String
  , playerTeam   :: Team
  , playerScores :: [Int]
  }

Custom `Show` instance for `Team`

instance Show Team where
  show t =
    "Team teamName " ++ show (teamName t) ++
    ", teamID "      ++ show (teamID t)
 
main =
  let t = Team "Red Dragons" 1
  in print t
-- Team teamName "Red Dragons", teamID 1

Custom `Show` instance for `Player`

instance Show Player where
  show p =
    "Player ID " ++ show (playerID p) ++
    ", Name "    ++ playerName p      ++
    ", Team "    ++ show (playerTeam p) ++
    ", Scores "  ++ show (playerScores p)
 
main =
  let t = Team "Red Dragons" 1
      p = Player 10 "Alice" t [20,30,40]
  in print p
-- Player ID 10, Name Alice, Team Team teamName "Red Dragons", teamID 1, Scores [20,30,40]

Custom `Eq` instance for `Player`

Rule:
Two players are equal if:

Their total score is the same
They belong to different teams

instance Eq Player where
  p1 == p2 =
    sum (playerScores p1) == sum (playerScores p2) &&
    teamID (playerTeam p1) /= teamID (playerTeam p2)
 
main =
  let t1 = Team "Red Dragons" 1
      t2 = Team "Blue Wolves" 2
      p1 = Player 1 "Alice" t1 [30,30]
      p2 = Player 2 "Bob"   t2 [60]
  in print (p1 == p2)
-- True

DarthDemono's Notes for ELTE

Explorer