Проблема Haskell с потенциальным обходным решением для пустых списков

Я определил функцию, которая получает тип данных и список.

getAux :: (Ord a) => SparseArray a -> [Bool] -> (Value a)
getAux (Node x left right) index
 | length(index) == 0 = x
 | head(index) == False = getAux (left) (tail(index))
 | head(index) == True = getAux (right) (tail(index))

Я повторяю эту функцию, передавая хвост из показатель Есть 3 возможных возврата: Если длина списка меньше или равна 1, он возвращает x (значение, хранящееся в узле). Если нет, он проверяет начало индекса и вызывает getAux с хвостом индекса.

Я попытался найти простое решение этой проблемы, добавив дополнительный элемент в конец индекса при вызове getAux. Вместо сравнения, если длина индекса равна 0, я сравниваю его с 1.

Когда я вызываю функцию, у меня есть:

getAux (Nodo x iz de) (num2bin(index) ++ [True])

Новый getAux:

getAux :: (Ord a) => SparseArray a -> [Bool] -> (Value a)
getAux (Node x left right) index
 | length(index) == 1 = x
 | head(index) == False = getAux (left) (tail(index))
 | head(index) == True = getAux (right) (tail(index))

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

Можете дать определение SparseArray? Вероятно, у него есть другой конструктор данных, кроме Node?

Willem Van Onsem 06.04.2022 12:45

Вы говорите: «Если длина списка меньше или равна 1, он возвращает x», а затем позже «Вместо сравнения, если длина индекса равна 0, я сравниваю его с 1». Разве вы не хотите вместо этого проверить, равна ли длина индекса 0 или 1?

Joe 06.04.2022 12:47

Можете ли вы дать конкретные данные, которые вызывают ошибку, которую вы видите? Я не могу воспроизвести: если я вызываю вашу функцию с [True] (т. е. в худшем случае, когда num2bin index возвращает []), я просто возвращаю x, который вставил Node x iz de, как и ожидал.

Daniel Wagner 06.04.2022 15:13
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
2
3
58
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вы вызываете это с помощью tail index, поэтому в конечном итоге вы достигаете пустого списка, следовательно, это объясняет, почему для последнего, если length index == 1 не удается, он попытается получить доступ head index и, следовательно, ошибка.

Но использование length не является хорошей идеей, так как оно работает в На) с н длиной списка, и обычно лучше выполнить сопоставление с образцом в списке, чем использовать head и tail, поскольку тогда гарантируется, что список имеет head и tail.

Таким образом, вы можете реализовать это как:

getAux :: SparseArray a -> [Bool] -> Value a
getAux (Node x _ _) [] = x
getAux (Node _ left right) (x:xs)
  | x = getAux right xs
  | otherwise = getAux left xs

Включив -Wincomplete-patterns [Haskell-docs] для компилятора, он предупредит вас о шаблонах, которые функция не охватывает. Например, если у вашего SparseArray есть дополнительный конструктор данных, то эти случаи не рассматриваются (пока).

Если я не ошибаюсь, если бы у него всегда была голова и хвост, он бы вошел в петлю

biomaticstudios 06.04.2022 13:56

@biomaticstudios: нет, пустой список всегда будет ошибкой как в head, так и в tail и, таким образом, не является полным. Вот почему некоторые программисты на Haskell считают их «небезопасными» и избегают их использования (а также length, поскольку это может застрять в бесконечном цикле для бесконечного списка и занимает На) времени).

Willem Van Onsem 06.04.2022 13:57

@biomaticstudios: именно поэтому использование сопоставления с образцом обычно является лучшей идеей: предложение срабатывает только в том случае, если совпадает с образцом, и поэтому мы уверены, что голова x и хвост xs существуют, если оно срабатывает для (x:xs). Более того, компилятор может выдавать предупреждения о незавершенных шаблонах: шаблоны значений, которые вообще не будут запускать предложение.

Willem Van Onsem 06.04.2022 14:01

Я не уверен, что куплюсь на это объяснение. Предположительно, если length index >= 1 с самого начала и length index == 1 терпит неудачу в каком-то рекурсивном вызове, то length index >= 1 по-прежнему имеет место. Поскольку они призывают вызывать его с num2bin index ++ [True] в качестве аргумента, для которого длина определенно >= 1, я не понимаю, как будет реализована небезопасная частичность head (или tail).

Daniel Wagner 06.04.2022 15:10

@DanielWagner Я не решаюсь не согласиться с кем-то, чье мнение я так высоко ценю, но лично мне нравится полагаться на компилятор, чтобы проверить, что я рассмотрел все случаи, а не на рассуждения, поэтому я бы предпочел сопоставление шаблонов с -Wincomplete-patterns на чем использовать head или tail, если я могу.

AndrewC 10.04.2022 01:43

@AndrewC Я не думаю, что что-либо из того, что ты сказал, противоречит тому, что я сказал! В частности, я не выносил оценочных суждений о той или иной части кода или о той или иной практике написания кода; только пояснений, что вызвало ошибку.

Daniel Wagner 10.04.2022 03:41

@DanielWagner Это облегчение!

AndrewC 10.04.2022 03:44

Другие вопросы по теме