Haskell — перебор и заполнение списка

avatar
singher
8 апреля 2018 в 02:48
390
1
2

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

У меня есть список целых чисел в файле myFile.txt, подобный следующему:

5
3 30
10 120
80 96
95 96
98 98

Где первое число в списке имеет целое число, чтобы сказать мне, сколько тестов будет следовать. В этом случае будет 5.

Я пытаюсь вернуть одно число (например: 20) для каждого теста (например: 3 30), которое означает общее количество множителей, находящихся в определенном диапазоне.

В качестве примера первого теста, 3 30:

  1. Мне нужно найти кратность каждого числа от 2 до первого числа (в данном случае 2 и 3) до значения 30. В этом случае:

    кратное 2: [2,4,6,8,10,12,14,16,18,20,22,24,26,28,30]

    Кратность 3: [3,6,9,12,15,18,21,24,27,30]

  2. Затем я нахожу сходство и подсчитываю все уникальные значения:

    [2,3,4,6,8,9,10,12,14,15,16,18,20,21,22,24,26,27,28,30]

Размер конечного списка в числе 2 равен 20, и это значение, которое я хотел бы вернуть

После сказанного у меня есть идеи, как реализовать эту реализацию. Мои планы по реализации этой реализации:

  1. Заполнить один список значениями, кратными числам которые меньше и равны первому полученному числу.
  2. Возьмите заполненный список и сгруппируйте его.
  3. Возьмите длину группы и напечатайте значение.

Для начала я сделал следующее, чтобы прочитать все входные данные, сохранить их в список и передать их функции для печати, чтобы подтвердить, что я получил правильное значение:

main = do  
    let myList = []
    handle <- openFile "myFile.txt" ReadMode
    contents <- hGetContents handle
    let singlewords = words contents
        myList = f singlewords
    printMyVals myList
    hClose handle

f :: [String] -> [Integer]
f = map read


printMyVals :: [Integer] -> IO()
printMyVals myList = 
    print myList

На данный момент я застрял.

Я пытаюсь выяснить, как мне перебрать значения моего списка и использовать эти значения для заполнения другого списка его кратными значениями, как указано выше.

Любая помощь по этому поводу?

Источник
max630
8 апреля 2018 в 08:14
0

поскольку вы умеете читать и печатать, было бы разумно исключить его из вопроса. Не могли бы вы выразить свою проблему только в ghci?

Ответы (1)

avatar
Adam Smith
8 апреля 2018 в 04:14
0

Итак, здесь есть несколько частей, и если разбить их на каждый шаг, каждый из них будет довольно простым. Где ввод на строку m и n:

  1. Найти все числа, кратные двум между 2 и n
  2. Найти все кратные m между m и n
  3. Отсортировать два списка вместе, удалив дубликаты
  4. Получить длину результирующего списка и распечатать его

Шаги 1 и 2 обрабатываются одной и той же функцией:

multiplesOfN n = [n, n+n..]

Это создаст бесконечный список значений кратных. Примените takeWhile (<=x), чтобы получить ограниченные значения. Для первой строки вашего ввода у вас будет:

twos   = takeWhile (<=30) . multiplesOfN $ 2
threes = takeWhile (<=30) . multiplesOfN $ 3

Затем вам нужно будет объединить два списка вместе, удалив дубликаты. Так как они оба представляют собой восходящие списки, это легко сделать в одношаговой сортировке слиянием.

mergesort :: (Eq a, Ord a) => [a] -> [a] -> [a]
mergesort [] ys = ys
mergesort xs [] = xs
mergesort xss@(x:xs) yss@(y:ys)
  | x < y     = x : mergesort xs yss
  | otherwise = y : mergesort xss ys
-- but this doesn't remove duplicates! Let's deal with that by
-- adding a new argument @lastValue@ and discarding if any match

uniqMergesort :: (Eq a, Ord a) => [a] -> [a] -> [a]
uniqMergesort xs [] = xs
uniqMergesort [] ys = ys
uniqMergesort xss@(x:xs) yss@(y:ys)
  | x < y     = x : go x xs  yss
  | otherwise = y : go y xss ys
  where
  go _ [] [] = []
  go lastValue (x:xs) []
    | lastValue == x =     go lastValue xs []
    | otherwise      = x : go lastValue xs []
  go lastValue [] (y:ys)
    | lastValue == y =     go lastValue [] ys
    | otherwise      = y : go lastValue [] ys
  go lastValue xss@(x:xs) yss@(y:ys)
    | x < y     = if   x == lastValue
                  then     go lastValue xs yss
                  else x : go x         xs yss
    | otherwise = if   y == lastValue
                  then     go lastValue xss ys
                  else y : go y         xss ys

Получение длины результирующего списка — это просто length, а извлечение значений из файла — это разбиение на строки, затем слова, затем чтение каждого слова.

main :: IO ()
main = do
  handle <- openFile "myFile.txt" ReadMode
  contents <- hGetContents handle
  let inputs  = map (map read . words) . lines $ tail contents
      results = [let xs = takeWhile (<=n) . multiplesOfN $ 2
                     ys = takeWhile (<=n) . multiplesOfN $ m
                 in  uniqMergesort xs ys | [m, n] <- inputs]
  mapM_ (print . length) results
  hClose handle
singher
8 апреля 2018 в 15:23
0

Спасибо за информацию @Adam Smith. При попытке запустить это я получаю сообщение об ошибке при запуске основной функции: "multi - st - overflow.hs: (36,3) - (42,46): неисчерпывающие шаблоны в функции go" Строка 36: go lastValue xss@(x:xs) yss@(y:ys) Строка 42: else y : go y xss ys Есть идеи, в чем может быть проблема?

Adam Smith
8 апреля 2018 в 23:12
0

@singher Ваш код или ваш пример ввода должны отличаться от того, что было дано. См. мой исполняемый пример на repl.it

singher
9 апреля 2018 в 13:28
0

Спасибо за обновления. Я действительно сделал ошибку в коде, и я попробовал ваш пример, и теперь он работает, однако внутри может быть небольшая логическая ошибка. Я обнаружил, что второй тест, ваш сообщает 67, по сравнению с тем, когда я проверяю его вручную, у меня есть 93 уникальных кратных. Я пытаюсь найти логическую ошибку внутри.

Adam Smith
9 апреля 2018 в 17:19
0

@singher Какой ввод дает 67? Он не включен в ваши тестовые входные данные.

singher
9 апреля 2018 в 17:47
0

Ввод: 10 120 - возврат 67

Adam Smith
9 апреля 2018 в 19:17
0

@singher возврат равен 60, и он должен быть 60 (поскольку 10 = 2*5, все x, где x = 10n также являются коэффициентами 2, поэтому результат просто length [2, 4..120], что тривиально равно 60).

singher
9 апреля 2018 в 20:29
0

Хм, так что, может быть, это немного по-другому. Идея заключалась бы в том, чтобы получить все кратные до первого числа. Во втором тесте с 10 120. Кратность 2[2,4,6,8,10,12 ... 120] Кратность 3[3,6,9,12,15,18,... 120] Кратность 4[4,8,12,16,20,24,28...120] До числа, кратного 10 [10,20,30,40...120]. Затем я объединяю их все только для уникальных значений. Имеет ли это смысл?

Adam Smith
9 апреля 2018 в 20:30
0

@singher о! Это не тот код, который я написал (в этом случае я проверил только 2 и 10). Рассмотрим let numbers = [[i, i+i..n] | i <- [2..m]] in foldr uniqMergeSort [] numbers

singher
9 апреля 2018 в 20:48
0

Это изменение в основном? "результаты = .." ?

singher
9 апреля 2018 в 21:15
0

О, отлично, похоже, теперь это действительно работает. Большое спасибо. Последний вопрос, если не возражаете. Что, если бы я хотел, чтобы это работало с очень большим числом, например, с таким тестом, как: 2 10000000000000000 - как такой тест сможет пройти?

Adam Smith
9 апреля 2018 в 23:52
0

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