Functional Programming for Basic Algorithms

Question

How good is 'pure' functional programming for basic routine implementations, e.g. list sorting, string matching etc.?

It's common to implement such basic functions within the base interpreter of any functional language, which means that they will be written in an imperative language (c/c++). Although there are many exceptions..

At least, I wish to ask: How difficult is it to emulate imperative style while coding in 'pure' functional language?

Answer 1

How good is 'pure' functional programming for basic routine implementations, e.g. list sorting, string matching etc.?

Very. I'll do your problems in Haskell, and I'll be slightly verbose about it. My aim is not to convince you that the problem can be done in 5 characters (it probably can in J!), but rather to give you an idea of the constructs.

import Data.List -- for `sort`
stdlistsorter :: (Ord a) => [a] -> [a]
stdlistsorter list = sort list

Sorting a list using the sort function from Data.List

import Data.List -- for `delete`
selectionsort :: (Ord a) => [a] -> [a]
selectionsort [] = []
selectionsort list = minimum list : (selectionsort . delete (minimum list) $ list)

Selection sort implementation.

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]
    in  smallerSorted ++ [x] ++ biggerSorted  

Quick sort implementation.

import Data.List -- for `isInfixOf`
stdstringmatch :: (Eq a) => [a] -> [a] -> Bool
stdstringmatch list1 list2 = list1 `isInfixOf` list2

String matching using isInfixOf function from Data.list

It's common to implement such basic functions within the base interpreter of any functional language, which means that they will be written in an imperative language (c/c++). Although there are many exceptions..

Depends. Some functions are more naturally expressed imperatively. However, I hope I have convinced you that some algorithms are also expressed naturally in a functional way.

At least, I wish to ask: How difficult is it to emulate imperative style while coding in 'pure' functional language?

It depends on how hard you find Monads in Haskell. Personally, I find it quite difficult to grasp.

Answer 2

1) Good by what standard? What properties do you desire?

List sorting? Easy. Let's do Quicksort in Haskell:

sort [] = []
sort (x:xs) = sort (filter (< x) xs) ++ [x] ++ sort (filter (>= x) xs)

This code has the advantage of being extremely easy to understand. If the list is empty, it's sorted. Otherwise, call the first element x, find elements less than x and sort them, find elements greater than x and sort those. Then concatenate the sorted lists with x in the middle. Try making that look comprehensible in C++.

Of course, Mergesort is much faster for sorting linked lists, but the code is also 6 times longer.

2) It's extremely easy to implement imperative style while staying purely functional. The essence of imperative style is sequencing of actions. Actions are sequenced in a pure setting by using monads. The essence of monads is the binding function:

(Monad m) => (>>=) :: m a -> (a -> m b) -> m b

This function exists in C++, and it's called ;.

A sequence of actions in Haskell, for example, is written thusly:

putStrLn "What's your name?" >>=
  const (getLine >>= \name -> putStrLn ("Hello, " ++ name))

Some syntax sugar is available to make this look more imperative (but note that this is the exact same code):

do {
  putStrLn "What's your name?";
  name <- getLine;
  putStrLn ("Hello, " ++ name);
}

Answer 3

Nearly all functional programming languages have some construct to allow for imperative coding (like do in Haskell). There are many problem domains that can't be solved with "pure" functional programming. One of those is network protocols, for example where you need a series of commands in the right order. And such things don't lend themselves well to pure functional programming.

I have to agree with Lothar, though, that list sorting and string matching are not really examples you need to solve imperatively. There are well-known algorithms for such things and they can be implemented efficiently in functional languages already.