Почему это не так хорошо напечатано?

Question

Я пишу функцию для создания набора всех перестановок строки - «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) пар. Итак, как это противоречиво?

Answer 1

Простое примечание: 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.

Надеюсь, это даст вам достаточно информации, чтобы исправить вашу ошибку.

Answer 2

Используя тот факт, что String s просто списки Char с вы могли быстро написать:

import Data.List 

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

предопределенная permutations фактически делает всю работу, которую вы хотите и nub просто удаляет дубликаты.

Обратите внимание, что этот подход не очень эффективен (O (n^2)) и должен использоваться только с небольшим количеством данных!