为什么这不是很好打字？

我正在写一个函数来产生一组字符串的所有排列 - “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)对。那么这是如何不一致？

来源

2013-04-10 Peter

我建议先开始使用基于列表的版本，然后调整它以便稍后使用“设置”，如果您决定真的需要它。列表不那么令人困惑（并且无论如何，对于像这样的少量数据来说'Set'并不是一个更快的事情）。 – 2013-04-10 03:41:52

快速提示：type String = [Char]。

Set.map需要一个正常的功能并将其映射到一个集合上。既然你有一个Set (Char, String)而你想要一个Set String，这个函数的类型应该是(Char, String) -> String。

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

这就是你的错误以稍微倾斜的方式说的：它预计有Set String，但得到了Set (Set String)。但是，由于错误大约是recurFunc，它只会告诉您有关该功能的问题：Set String应该只是String。

希望能给你足够的信息来解决你的错误。

来源

2013-04-10 02:57:43

使用的事实，String s为简单的Char小号列表，你可以快速地写：

import Data.List 

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

预定义的permutations实际上使所有你想要的工作和nub简单地删除重复项。

请注意，这种方法不是非常有效（O（n^2）），并且只能用于少量数据！

来源

2013-04-10 09:15:07 Jakub

为什么这不是很好打字？

回答

相关问题