Почему я не могу вызвать функцию быстрой сортировки (randomList 10)? - PullRequest
Новая
       65

Почему я не могу вызвать функцию быстрой сортировки (randomList 10)?

2 голосов
/ 20 апреля 2019

У меня есть следующий код: 

import Data.Array
import Control.Monad
import Data.Functor 
import System.Random (randomRIO)

randomList 0 = return []
randomList n = do
  r  <- randomRIO (1,6)
  rs <- randomList (n-1)
  return (r:rs) 

quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]  
    in  smallerSorted ++ [x] ++ biggerSorted
  1. randomList - создает список заданной длины и заполняет его случайными значениями;
  2. быстрая сортировка - быстро сортирует список.

Мне нужно применить сортировку к созданному массиву: quicksort (randomList 10), но возникает ошибка: 

"Couldn't match expected type‘ [a] ’with actual type IO [Int]’"

1 Ответ

3 голосов
/ 20 апреля 2019

Вы должны включить сигнатуры типов для всех имен верхнего уровня в вашей программе. если вы их не знаете, загрузите файл и спросите GHCi: Main> :t randomList. Затем скопируйте и вставьте его в файл (или сначала специализируйте его, как считаете нужным). Поместите подпись типа над именем, которое оно описывает.

GHCi говорит 

randomList ::
  (System.Random.Random t, Num t, Num a, Eq a) => a -> IO [t]

но вы, скорее всего, имели в виду 

randomList :: (System.Random.Random t, Num t) => Int -> IO [t]
randomList 0 = return []
randomList n = do
  r  <- randomRIO (1,6)    -- randomRIO (1,6) :: IO t  , r :: t
  rs <- randomList (n-1)   --             rs :: [t]
  return (r:rs)            --    r :: t , rs :: [t]

В общем 

randomRIO (1,6) :: (System.Random.Random a, Num a) => IO a

Вы разыгрываете 6-сторонний кубик n раз и собираете результаты в виде списка. Кстати, то же самое делает 

sequence $ replicate n (randomRIO (1,6))
===
replicateM n (randomRIO (1,6))

> :t \n -> replicateM n (randomRIO (1,6))
           :: (System.Random.Random a, Num a) => Int -> IO [a]

Затем GHCi также сообщает нам, что 

 quicksort :: Ord t => [t] -> [t]

Но randomList n - это IO [t], а не [t]. Чтобы получить значение [t], находящееся внутри IO [t], вам нужно сделать это на внутренней стороне : 

sortRandom :: (Ord t, Monad m) => m [t] -> m [t]
sortRandom randomlist = do
    xs <- randomlist        -- randomlist :: IO [t] , xs :: [t]
    let ys = quicksort xs
    return ys

Выше может быть сокращено до 

sortRandom :: (Ord t, Monad m) => m [t] -> m [t]
sortRandom = liftM quicksort     -- for monads

или 

sortRandom :: (Ord t, Functor f) => f [t] -> f [t]
sortRandom = fmap quicksort      -- for functors

, какой вы предпочитаете. Оба работают с IO, который является монадой, и любая монада также является функтором. Таким образом, в конце вы можете определить 

foo :: Int -> IO [Int]
foo n = liftM quicksort $ replicateM n (randomRIO (1,6))
...