爲什麼這不是很好打字？

我正在寫一個函數來產生一組字符串的所有排列 - 「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

爲什麼這不是很好打字？

回答

相關問題