Haskell, определяющий объем в использовании определений вложенной функции, где
Quicksort имеет O ( n 2 глоток>) время выполнения худшего случая и O ( журнал n n) среднее время выполнения случая. Однако it’s, выше сортировки слиянием во многих сценариях, потому что много факторов влияют на algorithm’s время выполнения, и, при взятии их всех вместе, quicksort, побеждает.
, В частности, часто заключенное в кавычки время выполнения сортировки алгоритмов посылает к количеству сравнений или количеству подкачек, необходимых работать для сортировки данных. Это - действительно хорошая мера производительности, тем более, что it’s независимый политик используемого оборудования разрабатывает. Однако другие вещи †“, такие как местность ссылки (т.е. мы читаем много элементов, которые находятся, вероятно, в кэше?) †“также играют важную роль на текущих аппаратных средствах. Quicksort в особенности требует небольшого дополнительного пространства и показывает хорошую местность кэша, и это делает его быстрее, чем сортировка слиянием во многих случаях.
, Кроме того, it’s очень легкий избежать quicksort’s времени выполнения худшего случая O ( n 2 глоток>) почти полностью при помощи соответствующего выбора pivot †“, такого как выбор его наугад (это - превосходная стратегия).
На практике, много современных реализаций quicksort (в особенности libstdc ++ ’s std::sort) на самом деле introsort, теоретический худший случай которого является O ( журнал n n), то же как сортировка слиянием. Это достигает этого путем ограничения глубины рекурсии и переключения на различный алгоритм ( пирамидальная сортировка ), как только это превышает журнал n.
2 ответа
Проблема с вашим кодом заключается в сигнатуре типа f1 с локальной областью действия. Он указывает, что f1 может принимать любой тип
f1 :: Eq a => a -> [a]
Несмотря на то, что это локальная функция, вы обобщили эту функцию, чтобы иметь возможность принимать тип, которого не будет в f, независимо от того, что эта функция получает, ДОЛЖНА исходить от f, поэтому сигнатура типа не нужно.
Просто удалите подпись типа f1.
Edit: Прочтите мой пост, он немного непонятен. a в f1 - это параметризованный тип, который может принимать что угодно, но переданные ему аргументы уже связаны в f. Таким образом, эта функция может получать только то, что получает ее родительская функция, сигнатура типа, которую вы ей даете, нарушает это правило. Надеюсь, это немного яснее.
Просто удалите подпись типа f1.
Редактировать: Прочтите мой пост, он немного непонятен. a в f1 - это параметризованный тип, который может принимать что угодно, но переданные ему аргументы уже связаны в f. Таким образом, эта функция может получать только то, что получает ее родительская функция, сигнатура типа, которую вы ей даете, нарушает это правило. Надеюсь, это немного яснее.
Просто удалите подпись типа f1.
Edit: Прочтите мой пост, он немного непонятен. a в f1 - это параметризованный тип, который может принимать что угодно, но переданные ему аргументы уже связаны в f. Таким образом, эта функция может получать только то, что получает ее родительская функция, сигнатура типа, которую вы ей даете, нарушает это правило. Надеюсь, это немного яснее.
Дэйв справа вверху. Другой способ думать об этом заключается в том, что хотя обе сигнатуры вашего типа относятся к переменной a , на самом деле это не одна и та же переменная типа. В нотации простых чисел Haskell обе сигнатуры могут быть более явно записаны как:
forall a. Уравнение a => a -> [a]
означает, что для обеих функций они могут принимать аргумент любого типа (в пределах Eq). Очевидно, здесь дело обстоит не так. В стандартном Haskell 98 единственный вариант - отказаться от сигнатуры типа для f1 . Но GHC (и другие?) Поддерживают переменные типа с лексической областью видимости . Так что вы можете написать
{-# LANGUAGE ScopedTypeVariables #-}
f :: forall a. Eq a => a -> [a]
f x = f1 x
where
f1 :: a -> [a]
f1 y = [ x, y ]
, и это будет нормально работать.