Ошибка в понимании вложенного списка в коде на Haskell

Question

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

something :: Int -> [Int]
something n = [[ 2 * x + 1 | x <- xs]|xs <- [3..n],i <- [1..],j <-[1..] ,xs == i+j+2*i*j,i<=j,i>=1]

Это то, что я вижу:

Couldn't match expected type `Int' with actual type `[t0]'
    In the expression: [2 * x + 1 | x <- xs]

Примечание: в этом произведении может быть гораздо больше ошибоккода.

Вот то, что я действительно пытаюсь научиться делать.Из списка всех натуральных чисел от 3 до n (который является входным значением Int для функции) я хочу извлечь только подмножество чисел, которое можно записать в виде i + j + 2 * i * j, где i, j - целые числаи я <= j и я> = 1.К этому списку подмножеств я хочу применить функцию 2 * x + 1 к каждому элементу x и вывести окончательный список.
Надеюсь, что это имеет смысл.

Answer 1

Прежде всего, у вас есть понимание вложенного списка, поэтому вы создаете список списков, поэтому тип возвращаемого значения должен быть [[Int]] (список списков целых), а не [Int] (список целых).

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

В ответ на ваше редактирование: я не понимаю, почему вы думали, что для этого вам нужны понимания вложенного списка. Если мы просто удалим вложение из вашего кода, мы получим что-то, что довольно близко к работе (я также переименовал xs в x, потому что вызов числа xs просто сбивает с толку - я также удалил условие что i равно как минимум 1, потому что это уже дано, поскольку вы берете i из списка [1..]):

[ 2 * x + 1 | x <- [3..n], i <- [1..],j <-[1..] ,x == i+j+2*i*j,i<=j]

Теперь это компилируется, но это будет цикл навсегда. Почему это цикл навсегда? Потому что вы берете I и J из бесконечных списков. Это означает, что он начнется с x = 3, i = 1, j = 1, а затем попробует все значения для j от 1 до бесконечности, прежде чем попробует следующее значение i (другими словами, он никогда не будет пытаться использовать следующее значение я).

Итак, нам нужно установить верхние границы i и j. Простая верхняя граница для выбора - x (если i или j больше x (и ни меньше 1), i+j+2*i*j не может быть равно x), поэтому Вы получите:

[ 2 * x + 1 | x <- [3..n], i <- [1..x],j <-[1..x], x == i+j+2*i*j, i<=j]

Это работает, но все же можно немного упростить: если мы возьмем j из списка [i..n] вместо [1..n], мы гарантируем, что j будет по крайней мере i, и мы не будем больше не нужно условие i<=j, поэтому мы можем написать:

[ 2 * x + 1 | x <- [3..n], i <- [1..x], j <-[i..x], x == i+j+2*i*j]

PS: Делать это таким образом (перебирать все x, а затем перебирать все возможные значения i и j для каждого x) немного неэффективно, так что вы можете пересмотреть свой подход. С другой стороны, если все, что вам нужно, это то, что работает, это нормально.

Answer 2

Во-первых, имя функции не должно быть в верхнем регистре.

xs <- [3..n] означает, что xs является Int, но x <- xs использует его как список.

Остальная часть понимания тоже выглядит немного странно. Если вы хотите объяснить, что именно вы хотите сделать, мы могли бы помочь немного больше. : -)

[редактировать]

Вы получаете бесконечный список своих номеров, используя [i+j+2*i*j| j <-[2..], i<-[1..(j-1)]], но он не отсортирован. [x| x <-[3..(2*n*n)], j <-[2..n], i<-[1..(j-1)], x==i+j+2*i*j] дает отсортированный список всех таких чисел, меньших 2n².

Answer 3

Давайте начнем с того, что у вас есть.

something n = [[ 2 * x + 1 | x <- xs]|xs <- [3..n],i <- [1..],j <-[1..] ,xs == i+j+2*i*j,i<=j,i>=1]

Основная проблема здесь в том, что вам не нужно понимание вложенного списка.

something n = [ 2 * x + 1 | x <- [3..n], i <- [1..], j <- [1..], x == i+j+2*i*j, i<=j, i>=1]

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

Давайте начнем с условий.Тестирование на i>=1 является излишним, учитывая, что i <- [1..].

something n = [ 2 * x + 1 | x <- [3..n], i <- [1..], j <- [1..], x == i+j+2*i*j, i<=j]

Аналогично, мы можем избавиться от условия i<=j, если мы начнем j с i вместо 1.

something n = [ 2 * x + 1 | x <- [3..n], i <- [1..], j <- [i..], x == i+j+2*i*j]

Должно быть понятно, что значения j больше (n - i) `div` (1 + 2 * i) не могут привести к x ≤ n.

something n = [ 2 * x + 1 | x <- [3..n], i <- [1..], j <- [i .. (n - i) `div` (1 + 2 * i)], x == i+j+2*i*j]

Аналогичнозначения i или n `div` 3 или выше не могут привести к x ≤ n.

something n = [ 2 * x + 1 | x <- [3..n], i <- [1 .. (n `div` 3) - 1], j <- [i .. (n - i) `div` (1 + 2 * i)],
                            x == i+j+2*i*j]

. На данный момент мы сделали достаточно для something, чтобы фактически генерировать результаты.Но есть повторяющиеся значения (например, когда (i, j) равно (1,7) или (2,4), вы получаете x = 22), что, я полагаю, вам не нужно.

Мы фильтруемих с использованием nub из Data.List.

something n = nub [ 2 * x + 1 | x <- [3..n], i <- [1 .. (n `div` 3) - 1],
                                j <- [i .. (n - i) `div` (1 + 2 * i)], x == i+j+2*i*j]

Нет необходимости проверять, что x удовлетворяет условию, когда мы могли бы построить x, чтобы удовлетворить это условие в первую очередь.(Вы захотите убедиться, что 3 ≤ x ≤ n все еще.) Это более эффективно.

something n = nub [ 2 * x + 1 | i <- [1 .. (n `div` 3) - 1], j <- [1 .. (n - i) `div` (1 + 2 * i)],
                                let x = i+j+2*i*j]

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

something n = sort $ nub [ 2 * x + 1 | i <- [1 .. (n `div` 3) - 1], j <- [1 .. (n - i) `div` (1 + 2 * i)],
                                       let x = i+j+2*i*j]

В точке стиля удвоение и добавление единицы - это отдельный расчет от гарантии того, что x может быть выражено как i + j + 2 * i * j, поэтому давайте разделим их.

something n = sort $ map f $ nub [ x | i <- [1 .. (n `div` 3) - 1], j <- [1 .. (n - i) `div` (1 + 2 * i)],
                                   let x = i+j+2*i*j]
  where f x = 2 * x + 1

Это позволяет нам избавиться от x из списка.

something n = sort $ map f $ nub [ i+j+2*i*j | i <- [1 .. (n `div` 3) - 1],
                                               j <- [1 .. (n - i) `div` (1 + 2 * i)]]
  where f x = 2 * x + 1

Готово.