The Thaumatorium:
Where the magic happens

The Different Types of Functions in Functional Programming

Author: NostraDavid
Published:
Updated:

In functional programming, the term "type" can be somewhat overloaded, especially in languages like Haskell. However, in this context, we are referring to different kinds of functions and their behaviors. A parser, for example, is a function that accepts strings as input and returns some data structure as output, typically a parse tree or a set of indices representing where parsing stopped successfully.

Types of Functions

Type Description Example Code
Pure Takes an input, returns an output – no side effects (data changes). 
f :: Int -> Int
f x = x
Predicate Takes an input, returns a Bool. 
f :: Int -> Bool
f x = x > 5
Recursive Like a Pure function, but also calls itself (at least once) with a subset of the original input. 
length :: [a] -> Int
length (x:xs) = 1 + length xs
Curried "Partial Application" means that a function receives only a part of the input, which makes it return a new function that still wants the rest of the input (imperative languages like C or Python always want all arguments at once) 
timesTwo :: Int -> Int
timesTwo = (2 *)

Example usage: As you can see, the * operator only has one input - It's been partially applied! When you look at the definition, you see that timesTwo expects at least one Int, which when applied, gets added at the end of the function:

timesTwo 3
-- { apply timesTwo }
2 * 3
-- { apply * }
6
Applicative Can take a variable amount of inputs and return an output. Uses the pure function and the <*> operator.

pure lifts a function into a wrapped type, and <*> accepts a wrapped type and a variable (also wrapped).
Monadic Takes an input, returns an output - can have side effects and uses either the bind >>= operator or do notation.

From: Haskell Wiki: All About Monads

maternalGrandfather :: Sheep -> Maybe Sheep
maternalGrandfather s = (return s) >>= mother >>= father
-- Alternatively
mothersPaternalGrandfather :: Sheep -> Maybe Sheep
mothersPaternalGrandfather s = do m  <- mother s
                                  gf <- father m
                                  father gf
Parser Combinator Accepts several parsers as input and returns a new parser as output.

From: Wikipedia: Parser Combinator

A parser is a function accepting strings as input and returning some structure as output, typically a parse tree or a set of indices representing where parsing stopped successfully in the string.