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.