Нахождение кратчайшего списка в списке списков в Haskell - PullRequest
Новая
       11

Нахождение кратчайшего списка в списке списков в Haskell

0 голосов
/ 30 октября 2018

У меня возникли трудности с программой, написанной на Haskell. Идея заключается в том, чтобы рекурсивно найти самый короткий список в списке списков и вернуть его. Мне удалось написать программу, но я не могу понять, что я сделал в ней неправильно. Вот ошибки, которые я получаю, когда пытаюсь его скомпилировать:

  • Не удалось сопоставить тип «a» с «[[a]]», «a» - это жесткая переменная типа, связанная сигнатурой типа для: shorttest :: forall a. [[a]] -> [a] по адресу shorttest.hs: 1: 13. Ожидаемый тип: [[[a]]], фактический тип: [a]
  • В первом аргументе «кратчайшего», а именно «у». В первом аргументе «(:)», а именно «кратчайший y». В выражении: кратчайший у: [список]
  • Соответствующие привязки включают в себя список :: [[a]] (связан с кратчайшим.hs: 4: 15), y :: [a] (связан с кратчайшим.hs: 4: 13), x :: [a] (связано с кратчайшим.hs: 4: 11), самое короткое :: [[a]] -> [a] (связано с кратчайшим.hs: 2: 1).

Вот код, который я использую: 

shortest :: [[a]] -> [a]
shortest [] = []
shortest [y] = y
shortest (x:y:list)
   | length x > length y = shortest y:[list]
   | otherwise = shortest x:[list]

Если бы кто-нибудь мог дать мне какие-либо указания относительно того, где я иду не так, это было бы очень ценно!

Ответы [ 3 ]

0 голосов
/ 30 октября 2018

list уже хвост вашего ввода; вам не нужно (и не нужно) оборачивать его в другой список. 

shortest (x:y:list) = shortest $ (if length x > length y then y else x) : list

На каждом шаге вопрос только в том, какой элемент, x или y, вы удаляете из ввода для рекурсивного вызова.

Другой способ, который не требует двух базовых случаев, - это просто сравнить заголовок списка с результатом повторения в хвосте. 

shortest [] = []
shortest (x:xs) = let s = shortest xs
                  in if length s < length x then s else x

Наконец, кортежи сравниваются лексикографически, поэтому вы также можете обойтись без явной рекурсии, пометив каждый список его длиной, найдя наименьшее помеченное значение, а затем извлекая исходный список. 

shortest = snd . minimum . map (\x -> (length x, x))

Используя Control.Arrow, вы можете записать аргумент в map как (length &&& id).

Предостережение для последнего подхода: поскольку списки также сравниваются лексикографически, конечный результат, если у вас есть несколько списков с наименьшей длиной, будет зависеть от того, как сравниваются сами значения списка. Первые два примера, напротив, стабильны; первый такой короткий список возвращается.

Даниэль Вагнер указывает на лучшее решение для использования minimum, заключающееся в том, чтобы обернуть каждый элемент в значение Arg, позволяющее сравнивать два списка только по их длине, без учета списков ' содержание. 

import Data.Semigroup
shortest xs = x where Arg _ x = minimum [Arg (length x) x | x <- xs]

Arg - это в основном двухэлементный тип продукта, который только использует первый элемент для своего экземпляра Ord, в отличие от (,), который использует оба.

0 голосов
/ 30 октября 2018 
  shortest []=[]
  shortest [y] = y
  shortest (x:y:list)
   |length x > length y = shortest (y:list)            
   |otherwise = shortest (x:list)

Это работает :), также стоит упомянуть, если у вас есть 2 или несколько элементов в списке, которые являются «самыми короткими», первый элемент всегда будет появляться.

т.е. 

   Prelude>shortest[[1],[2],[3]]
   [1]
0 голосов
/ 30 октября 2018

Я думаю, вам нужны круглые скобки: shortest (y:list) и то же самое для случая x.

Приоритет : делает его читаемым как (shortest y) : list

...