Выведенный тип, кажется, обнаруживает бесконечный цикл, но что действительно происходит?
Вероятно, рабочее решение для Perl, если строка находится на одной строке:
my $NesteD ;
$NesteD = qr/ \{( [^{}] | (??{ $NesteD }) )* \} /x ;
if ( $Stringy =~ m/\b( \w+$NesteD )/x ) {
print "Found: $1\n" ;
}
РЕДАКТИРОВАНИЕ HTH
: проверка:
- http://dev.perl.org/perl6/rfc/145.html
- рубиновая информация: http://www.ruby-forum.com/topic/112084 [еще 1110] жемчуг: http://www.perlmonks.org/?node_id=660316
- еще больше жемчуга: https://metacpan.org/pod/Text:: Сбалансированный
- жемчуг, жемчуг, жемчуг: http://perl.plover.com/yak/regex/samples/slide083.html
И еще одна вещь Torsten Marek (кто указал правильно, что это больше не regex):
2 ответа
Это действительно замечательный пример; обнаруживается бесконечный цикл, по сути, во время компиляции ! В этом примере нет ничего особенного в выводе Хиндли – Милнера; это происходит как обычно.
Обратите внимание, что ghc правильно получает типы split и merge :
*Main> :t split
split :: [a] -> ([a], [a])
*Main> :t merge
merge :: (Ord t) => [t] -> [t] -> [t]
Теперь, когда дело доходит до mergesort , он в общем случае является функцией t 1 → t 2 для некоторых типов t 1 и t 2 . Затем он видит первую строку:
mergesort [] = []
и понимает, что t 1 и t 2 должны быть типами списков, скажем, t 1 = [t 3 ] и t 2 = [t 4 ]. Таким образом, сортировка слиянием должна быть функцией [t 3 ] → [t 4 ]. Следующая строка
mergesort xs = merge (mergesort p) (mergesort q)
where (p,q) = split xs
сообщает, что: тип слияния (mergesort p) (mergesort q) тот же, что и у обоих его входов, а именно [t 4 ]. Это соответствует ранее известному типу [t 3 ] → [t 4 ] для mergesort , поэтому больше не нужно делать никаких выводов и «унификация "часть алгоритма Хиндли-Милнера завершена. mergesort имеет тип [t 3 ] → [t 4 ] с t 4 в Ord .
Вот почему вы получаете:
*Main> :t mergesort
mergesort :: (Ord a) => [t] -> [a]
(Приведенное выше описание с точки зрения логического вывода эквивалентно тому, что делает алгоритм, но конкретная последовательность шагов, которым следует алгоритм, просто указана, например, на странице Википедии.)
Это соответствует ранее известному типу [t 3 ] → [t 4 ] для mergesort , поэтому больше не нужно делать никаких выводов и «унификация "часть алгоритма Хиндли-Милнера завершена. mergesort имеет тип [t 3 ] → [t 4 ] с t 4 в Ord .
Вот почему вы получаете:
*Main> :t mergesort
mergesort :: (Ord a) => [t] -> [a]
(Приведенное выше описание с точки зрения логического вывода эквивалентно тому, что делает алгоритм, но конкретная последовательность шагов, которым следует алгоритм, просто указана, например, на странице Википедии.)
Это соответствует ранее известному типу [t 3 ] → [t 4 ] для mergesort , поэтому больше не нужно делать никаких выводов и «унификация "часть алгоритма Хиндли-Милнера завершена. mergesort имеет тип [t 3 ] → [t 4 ] с t 4 в Ord .
Вот почему вы получаете:
*Main> :t mergesort
mergesort :: (Ord a) => [t] -> [a]
(Приведенное выше описание с точки зрения логического вывода эквивалентно тому, что делает алгоритм, но конкретная последовательность шагов, которым следует алгоритм, просто указана, например, на странице Википедии.)
mergesort имеет тип [t 3 ] → [t 4 ] с t 4 в Ord .
Вот почему вы получаете:
*Main> :t mergesort
mergesort :: (Ord a) => [t] -> [a]
(Приведенное выше описание с точки зрения логического вывода эквивалентно тому, что делает алгоритм, но конкретная последовательность шагов, которой следует алгоритм, просто указана, например, на странице Википедии.)
mergesort имеет тип [t 3 ] → [t 4 ] с t 4 в Ord .
Вот почему вы получаете:
*Main> :t mergesort
mergesort :: (Ord a) => [t] -> [a]
(Приведенное выше описание с точки зрения логического вывода эквивалентно тому, что делает алгоритм, но конкретная последовательность шагов, которым следует алгоритм, просто указана, например, на странице Википедии.)
Этот тип можно вывести, поскольку он видит, что вы передаете результат mergesort в merge , который, в свою очередь, сравнивает заголовки списков с <, который является частью класса типов Ord. Таким образом, вывод типа может привести к тому, что он должен вернуть список экземпляра Ord. Конечно, поскольку он фактически повторяется бесконечно, мы не можем сделать никаких выводов о типе, который он фактически не возвращает.