Эффективен ли этот код на Haskell?

Question

В качестве упражнения для начинающих я реализовал следующую функцию для поиска n-го элемента в списке:

elem_at (h:_) 0 = h  
elem_at (_:t) n = elem_at t (n-1)  
elem_at _ _     = error "Index out of bounds"

Однако, если я вызову: elem_at [1,2,3,4] 5, правильно ли, что он вернет «Индекс вне границ» только после того, как пройдёт весь список, так что последняя строка соответствует шаблону _ _ с [] 1?В целом, если бы список был большой , разве это не было бы проблемой производительности?Может ли GHC как-то оптимизировать эту ситуацию?

Answer 1

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

elem_at xs n | n < 0 =  error "elem_at: negative index"

И вы можете добавить конкретное совпадение для пустого списка:

elem_at [] _         =  error "elem_at: index too large"

И базовый и индуктивный корпус:

elem_at (x:_)  0         =  x
elem_at (_:xs) n         =  elem_at xs (n-1)

и у вас есть определение индексации списка Prelude, оператор (!!).

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

Answer 2

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