基本算法的功能编程

Question

基本例程实现的"纯"函数式编程有多好,例如列表排序,字符串匹配等？

在任何函数式语言的基本解释器中实现这些基本函数是很常见的,这意味着它们将用命令式语言(c/c ++)编写.虽然有很多例外..

至少,我想问一下:在用"纯粹的"功能语言编码时,模仿命令式的风格有多难？

Answer 1

1)标准好吗？你想要什么属性？

列表排序？简单.让我们在Haskell做Quicksort:

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

此代码具有非常易于理解的优点.如果列表为空,则对其进行排序.否则,调用第一个元素x,找到小于x的元素并对它们进行排序,找到大于x的元素并对它们进行排序.然后将排序列表与中间的x连接起来.尝试在C++中使其看起来易于理解.

当然,Mergesort对链表的排序要快得多,但代码也要长6倍.

2)在保持纯粹功能的同时实现命令式风格非常容易.命令式风格的本质是行动的顺序.使用monad在纯设置中对操作进行排序.monads的本质是绑定功能:

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

这个函数存在于C++中,它被调用;.

例如,Haskell中的一系列动作就是这样编写的:

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

一些语法糖可用于使这看起来更加迫切(但请注意,这是完全相同的代码):

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

Answer 2

基本例程实现的"纯"函数式编程有多好,例如列表排序,字符串匹配等？

非常.我会在Haskell中解决你的问题,对此我会略显冗长.我的目的不是说服你,问题可以用5个字符完成(它可能在J!中),而是让你了解这些结构.

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

使用sort函数从中排序列表Data.List

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

选择排序实现.

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  

快速排序实施.

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

使用isInfixOf函数的字符串匹配Data.list

在任何函数式语言的基本解释器中实现这些基本函数是很常见的,这意味着它们将用命令式语言(c/c ++)编写.虽然有很多例外..

要看.有些功能更加自然地表达出来.但是,我希望我已经说服你,某些算法也以功能的方式自然地表达出来.

至少,我想问一下:在用"纯粹的"功能语言编码时,模仿命令式的风格有多难？

这取决于你在Haskell中找到Monads的难度.就个人而言,我觉得很难掌握.