Functional Programming for Basic Algorithms

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 wit开发者_如何学Pythonhin 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?

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.

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);
}

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.

I think that 'algorithms' (e.g. method bodies and basic data structures) are where functional programming is best. Assuming nothing completely IO/state-dependent, functional programming excels are authoring algorithms and data structures, often resulting in shorter/simpler/cleaner code than you'd get with an imperative solution. (Don't emulate imperative style, FP style is better for most of these kinds of tasks.)

You want imperative stuff sometimes to deal with IO or low-level performance, and you want OOP for partitioning the high-level design and architecture of a large program, but "in the small" where you write most of your code, FP is a win.

See also

How does functional programming affect the structure of your code?

It works pretty well the other way round emulating functional with imperative style.

Remember that the internal of an interpreter or VM ware so close to metal and performance critical that you should even consider going to assember level and count the the clock cycles for each instruction (like Smalltalk Dophin is just doing it and the results are impressive). CPU's are imperative.

But there is no problem to do all the basic algorithm implementation - the one you mention are NOT low level - they are basics.

I don't know about list sorting, but you'd be hard pressed to bootstrapp a language without some kind of string matching in the compiler or runtime. So you need that routine to create the language. As there isn't a great deal of point writing the same code twice, when you create the library for matching strings within the language, you call the code written earlier. The degree to which this happens in successive releases will depend on how self hosting the language is, but unless that's a strong design goal there won't be any reason to change it.