Определение оператора для доступа к многомерному массиву

У меня возникла идея определить оператор, который принимает (возможно) многомерный список и список индексов и возвращает элемент. Моя прото попытка была:

(!!!) xs [i]            = xs !! i
(!!!) xs (cI : restI)   = (xs !! cI) !!! restI

Оглядываясь назад, это, очевидно, имеет много проблем. Сначала я не мог определить сигнатуру типа, потом понял, что в строке 2 возвращаемый тип (xs ​​!! cI) будет постоянно меняться и не всегда может быть даже списком (на последней «итерации»)

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

[[1,2,3],[4,5,6],[7,8,9]] !! 1 !! 1 = 5

И понял, что это очень похоже на складку, поэтому я попробовал:

(!!!) xxs inds = foldl (!!) xxs inds
or simply (!!!) = foldl (!!) 

Но я получаю ту же ошибку, что и при первой попытке; что я пытаюсь построить бесконечный тип.

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

В качестве примера я стремился к следующему:

[[1,2,3],[4,5,6],[7,8,9]] !!! [1,1] = 5

multidimensional-array haskell
person Carcigenicate    schedule 31.08.2014    source источник
comment
Вы пытаетесь создать функцию, которая работает с 2 измерениями или n измерениями?   -  person    schedule 31.08.2014
comment
@Balthamos Произвольные размеры. Глубина массива будет определяться длиной списка заданных индексов. Как и в последнем примере, который я привел, я предоставил 2 индекса ([1,1]), поэтому данный массив должен быть двумерным. Если бы я дал индексы [2,1,1], список должен был бы быть трехмерным.   -  person Carcigenicate    schedule 31.08.2014
comment
Вы хотели бы сделать что-то похожее на этот вопрос: stackoverflow.com/questions/5994051/   -  person    schedule 31.08.2014
comment
Я бы хотел сохранить исходную структуру, хотя. И этот вопрос больше из любопытства, чем что-либо. Это началось с того, что потребовался оператор 2D-индекса, но это было легко. Изначально это казалось выполнимым, поэтому я решил попробовать. Теперь, когда проблемы ясны, мне любопытно, есть ли способ сделать это возможным.   -  person Carcigenicate    schedule 31.08.2014
comment
@Carcigenicate Чтобы элегантно решить проблему такого рода в системе типов, подобной Haskell, вам действительно нужны зависимые типы. Зависимые типы — это те, которые зависят от значений во время выполнения. Вы хотите проиндексировать n-мерный список, используя список из n элементов, поэтому тип функции зависит от длины переданного ей списка индексации. Хотя в Haskell можно получить некоторые из этих функций, система типов не поддерживает их как первоклассные и требует расширений, большого количества шаблонов и некоторых трюков. Если вам интересно, посмотрите на языки Agda или Idris.   -  person bheklilr    schedule 31.08.2014
comment
@bheklilr Спасибо. Как я уже сказал, это не то, что мне действительно нужно; вопрос был чисто из любопытства. На самом деле, я все равно не вижу необходимости в этой функции, если только у вас нет программы, в которой одновременно используется множество массивов разной глубины, и вам нужна универсальная функция для доступа к ним. Мне просто нужен был оператор 2D-индекса, и я решил попробовать сделать его универсальным. Если для этого требуется сложный хак, я не очень заинтересован в его реализации, но если кому-то нужна проблема, я хотел бы увидеть решение (это то, что публикуется в Codes golf?)   -  person Carcigenicate    schedule 31.08.2014

Ответы (1)


arrow_upward
8
arrow_downward

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

data Nat = Z | S Nat

infixr 5 :>
data Vector (n :: Nat) a where 
  Nil :: Vector Z a 
  (:>) :: a -> Vector n a -> Vector (S n) a

Тогда ваша функция

(!!!) a Nil = a 
(!!!) a (i :> is) = (a !! i) !!! is

Вы заметите, что это не компилируется. Это связано с тем, что типы a в первой и второй строках различны. Тип a должен зависеть от типа индексов, и вы должны указать компилятору, как именно они зависят от него. Зависимость довольно проста; когда есть n индексов, должен быть список из n измерений:

type family Dimension (n :: Nat) (v :: * -> *) (x :: *) :: * where 
  Dimension     Z v x = x 
  Dimension (S n) v x = v (Dimension n v x)

Тогда тип вышеизложенного довольно просто

(!!!) :: Dimension n [] a -> Vector n Int -> a

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

person user2407038    schedule 31.08.2014