Haskell: между списком и кортежем

Мне нужна функция +++, которая добавляет два математических вектора.

Я мог бы реализовать векторы как [x, y, z] и использовать:

(+++) :: (Num a) => [a] -> [a] -> [a]
(+++) = zipWith (+)

И, следовательно, разместим любой n-мерный вектор (так что это будет работать и для [x, y]).

Или я мог бы реализовать векторы как (x, y, z) и использовать:

type Triple a = (a, a, a)

merge :: (a -> b -> c) -> Triple a -> Triple b -> Triple c
merge f (a, b, c) (x, y, z) = (f a x, f b y, f c z)

(+++) :: (Num a) => Triple a -> Triple a -> Triple a
(+++) = merge (+)

Конечно, это немного сложнее, но при реализации всех других векторных функций это не имеет значения (50 строк вместо 40).

Проблема с подходом к списку заключается в том, что я могу добавить 2D-вектор с 3D-вектором. В этом случае zipWith просто отключит компонент 3D-вектора z. Хотя это может иметь смысл (более вероятно, что он должен расширить 2D-вектор до [x, y, 0]), для других функций я думаю, что это может быть проблематично, чтобы либо произойти молча. Проблема с подходом к кортежу заключается в том, что он ограничивает вектор тремя компонентами.

Интуитивно я бы подумал, что было бы более целесообразно представлять векторы как (x, y, z), так как математический вектор имеет фиксированное число компонентов, и на самом деле не имеет смысла сглаживать (дописывать) компонент вектору.

С другой стороны, хотя очень маловероятно, что мне понадобится что-то другое, кроме 3D-векторов, это не кажется правильным для ограничения этого.

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

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

Ответы

Ответ 1

Ответы Landei и leftaroundabout хорошие (спасибо вам обоим), и я думаю, я должен был понять, что это будет не так просто, как я надеялся. Попытка сделать любой из предложенных мной вариантов делает сложный код, который не будет проблемой сам по себе, за исключением того, что кажется, что код пользователя не будет очень красивым, чтобы смотреть на него.

Думаю, я решил пойти с кортежами и придерживаться только трехмерных векторов, просто потому, что кажется более семантически правильным, чем использование списков. Тем не менее, я заканчиваю повторное внедрение map, zipWith, sum и других для троек. Я хочу придерживаться простоты - я чувствую, что если бы у меня был веский аргумент, чтобы думать о векторах как о списках, то это решение получило бы лучшую работу (при условии, что я не буду смешивать измерения)... Когда я на самом деле использую векторы, хотя функции будут принимать 3D-вектор в качестве аргумента, а не один из переменных измерений, а Num a => [a] не может обеспечить его выполнение.

Ответ 2

Вы можете использовать программирование уровня. Сначала нам нужно сделать каждый натуральный номер отдельным типом. Следуя определению натуральных чисел Пеано, Z 0, а S x - x + 1

data Z = Z
data S a = S a

class Nat a
instance Nat Z
instance (Nat a) => Nat (S a)

Теперь мы можем использовать тип Vec для простого переноса списка, но для отслеживания его размера с помощью Nat. Для этого мы используем интеллектуальные конструкторы nil и <:> (поэтому вы не должны экспортировать конструктор данных Vec из своего модуля)

data Vec a = Vec a [Int]

nil = Vec Z []

infixr 5 <:>
x <:> (Vec n xs) = Vec (S n) (x:xs)

Теперь мы можем определить функцию add, которая требует, чтобы два вектора имели одинаковый Nat:

add :: Nat a => Vec a -> Vec a -> Vec a
add (Vec n xs) (Vec _ ys) = Vec n (zipWith (+) xs ys)

Теперь у вас есть векторный тип с информацией о длине:

toList (Vec _ xs) = xs
main = print $ toList $ add (3 <:> 4 <:> 2 <:> nil) (10 <:> 12 <:> 0 <:> nil)

Конечно, наличие векторов с разной длиной здесь приведет к ошибке компиляции.

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

Ответ 3

Самый простой способ - поместить оператор +++ в класс типа и сделать различные экземпляры размеров кортежей:

{-# LANGUAGE FlexibleInstances #-}   -- needed to make tuples type class instances

class Additive v where
  (+++) :: v -> v -> v

instance (Num a) => Additive (a,a) where
  (x,y) +++ (ξ,υ)  =  (x+ξ, y+υ)
instance (Num a) => Additive (a,a,a) where
  (x,y,z) +++ (ξ,υ,ζ)  =  (x+ξ, y+υ, z+ζ)
...

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

Обобщение этого на использование функции типа merge в действительном классе типов также возможно: в этом случае вам нужно указать экземпляр класса как конструктор типа (например, монаду списка).

class Mergable q where
  merge :: (a->b->c) -> q a -> q b -> q c

instance Mergable Triple where
  merge f (x,y,z) (ξ,υ,ζ) = (f x ξ, f y υ, f z ζ)

а затем просто

(+++) :: (Mergable q, Num a) => q a -> q b -> q c
+++ = merge (+)

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

newtype Triple a = Triple(a,a,a)

а затем

instance Mergable Triple where
  merge f (Triple(x,y,z)) (Triple((ξ,υ,ζ)) = Triple(f x ξ, f y υ, f z ζ)

что, конечно, не так приятно смотреть.

Ответ 4

Поскольку OP хотел более легкий подход, я бы использовал связанные типы.

class VecMath a b where
    type Res a b :: *
    (+++) :: a -> b -> Res a b

instance Num a => VecMath (a,a,a) (a,a,a) where
    type Res (a,a,a) (a,a,a) = (a,a,a)
    (x1,y1,z1) +++ (x2,y2,z2) = (x1+x2, y1+y2, z1+z2)

instance Num a => VecMath (a,a) (a,a,a) where
    type Res (a,a) (a,a,a) = (a,a,a)
    (x1,y1) +++ (x2,y2,z) = (x1+x2, y1+y2, z)

instance Num a => VecMath (a,a,a) (a,a) where
    type Res (a,a) (a,a,a) = (a,a,a)
    -- (+++) analog
instance Num a => VecMath (a,a) (a,a) where
    type Res (a,a) (a,a) = (a,a)
    -- ...

Res - это функция типа, здесь, по существу, приводя к "более крупным" типам аргументов. Преимущество состоит в том, что вы все еще можете работать с обычными старыми кортежами, как будто VecMath не существует. Темная сторона - это экспоненциальный взрыв экземпляров, которые вы должны написать, если рассмотреть возможность добавления новых типов в домен Res. Для получения дополнительной информации см. this.