0

我正在编写一个函数来生成一组字符串的所有排列——“foo”应该返回 {“foo”、“ofo”、“oof”}。我已经在 Clojure 中这样做了，所以我知道这种方法是正确的，但我想我会在 Haskell 中进行练习。下面是我所拥有的。

import qualified Data.Set as Set

substr :: String -> Int -> Int -> String
substr s start end = take (end - start) . drop start $ s

substrs :: String -> Set.Set (Char, String)
substrs s = let len = length s
            in foldl (\acc x -> Set.insert (s !! x, ((substr s 0 x)++(substr s (succ x) len))) acc) Set.empty [0..len-1]

-- not sure about the type
permute [] = Set.empty
permute s = Set.map recurFunc (substrs s)
  where recurFunc (c, s) = Set.map (c:) (permute s)

main :: IO ()
main = print $ permute "foo!"

当然，这不会编译，否则我不会问。我得到：

permute.hs:12:21:
Couldn't match expected type `String'
            with actual type `Set.Set [Char]'
Expected type: (Char, String) -> String
  Actual type: (Char, String) -> Set.Set [Char]
In the first argument of `Set.map', namely `recurFunc'
In the expression: Set.map recurFunc (substrs s)

Set.map被声明为(a -> b) -> Set a -> Set b。据我所知，recurFunc接受一组(Char, String)对，并返回一组字符串。substrs返回一组(Char, String)对。那么这怎么不一致呢？

4

2 回答 2

6

只是一个简短的说明：type String = [Char]。

Set.map接受一个普通函数并将其映射到一个集合上。既然你有一个Set (Char, String)并且你想要一个Set String，这个函数应该有类型(Char, String) -> String。

但是，您recurFunc返回一个集合而不仅仅是一个字符串。也就是说，它有一个类型(Char, String) -> Set String。（我认为类型实际上更通用一点，但这并不重要。）所以当你将它映射到一个集合上时，你会得到一组集合：类似于Set (Set String).

这就是您的错误以略微倾斜的方式所说的：它期望 aSet String但得到了Set (Set String). 但是，由于错误是 about recurFunc，它只告诉您函数的问题：Set String应该只是String。

希望这可以为您提供足够的信息来修复您的错误。

于 2013-04-10T02:57:43.823 回答
1

String使用s 只是 s 列表的事实，Char您可以快速编写：

import Data.List

permute = Eq a => [a] -> [[a]]
permute = nub . permutations

预定义permutations实际上可以完成您想要的所有工作，并且nub只需删除重复项。

请注意，这种方法不是很有效（O(n^2)），只能用于少量数据！

于 2013-04-10T09:15:07.420 回答