Haskell - Воспроизвести форму numpy

Question

Попадая в Haskell, я пытаюсь воспроизвести что-то вроде numpy, изменяющего со списками. В частности, с учетом плоского списка, преобразовать его в n-мерный список:

import numpy as np

a = np.arange(1, 18)
b = a.reshape([-1, 2, 3])

# b = 
# 
# array([[[ 1,  2,  3],
#         [ 4,  5,  6]],
# 
#        [[ 7,  8,  9],
#         [10, 11, 12]],
# 
#        [[13, 14, 15],
#         [16, 17, 18]]])

Мне удалось воспроизвести поведение с фиксированными индексами, например:

*Main> reshape23 [1..18]
[[[1,2,3],[4,5,6]],[[7,8,9],[10,11,12]],[[13,14,15],[16,17,18]]]

Мой код :

takeWithRemainder :: (Integral n) => n -> [a] -> ([a], [a])
takeWithRemainder _ [] = ([], [])
takeWithRemainder 0 xs = ([], xs)
takeWithRemainder n (x:xs) = (x : taken, remaining)
                                where (taken, remaining) = takeWithRemainder (n-1) xs

chunks :: (Integral n) => n -> [a] -> [[a]]
chunks _ [] = []
chunks chunkSize xs = chunk : chunks chunkSize remainderOfList
                        where (chunk, remainderOfList) = takeWithRemainder chunkSize xs

reshape23 = chunks 2 . chunks 3

Теперь я не могу найти способ обобщить это в произвольную форму. Моя оригинальная идея заключалась в том, чтобы сделать сгиб:

reshape :: (Integral n) => [n] -> [a] -> [b]
reshape ns list = foldr (\n acc -> (chunks n) . acc) id ns list

Но, как бы я ни go об этом, я всегда получаю ошибку типа от компилятора. Насколько я понимаю, проблема в том, что в какой-то момент тип для acc определяется как id, то есть a -> a, и ему не нравится тот факт, что список функций в сгибе имеет подпись другого типа (хотя и совместимая с композицией). Я сталкиваюсь с той же проблемой, пытаясь реализовать это с помощью рекурсии самостоятельно, а не сгибанием Это смутило меня, потому что изначально я предполагал, что сигнатура типа [b] в reshape будет заменять «другой, диссоциированный тип», который может быть любым от [[a]] до [[[[[a]]]]].

Как я ошибаюсь по этому поводу? Есть ли способ на самом деле достичь того поведения, которое я намеревался, или это просто неправильно - хотеть такого рода «Dynami c» поведение с самого начала?

Answer 1

Здесь есть две детали, которые качественно отличаются от Python, в конечном итоге вытекающие из динамического набора c против stati c.

Первая , которую вы заметили самостоятельно: на каждом этапе чанкинга результирующий тип отличается от типа ввода. Это означает, что вы не можете использовать foldr, потому что он ожидает функцию одного указанного c типа. Вы можете сделать это через рекурсию.

Вторая проблема немного менее очевидна: тип возврата вашей функции reshape зависит от первого аргумента. Например, если первый аргумент [2], тип возвращаемого значения [[a]], но если первый аргумент [2, 3], тип возвращаемого значения [[[a]]]. В Haskell все типы должны быть известны во время компиляции. А это значит, что ваша reshape функция не может принимать первый аргумент, определенный во время выполнения. Другими словами, первый аргумент должен быть на уровне типа.

Значения уровня типа могут быть вычислены с помощью функций типа (также называемых «семействами типов»), но поскольку это не просто , тип (т.е. у вас также есть значение для вычисления), естественный (или единственный?) механизм для этого является классом типа.

Итак, сначала давайте определим наш класс типов:

class Reshape (dimensions :: [Nat]) from to | dimensions from -> to where
    reshape :: from -> to

Класс имеет три параметра: dimensions вида [Nat] - это массив чисел уровня типа, представляющий желаемые измерения. from является типом аргумента, а to является типом результата. Обратите внимание, что, хотя известно, что тип аргумента всегда [a], мы должны иметь его здесь как переменную типа, потому что в противном случае наши экземпляры класса не смогут корректно соответствовать тому же a между аргументом и результат.

Кроме того, класс имеет функциональную зависимость dimensions from -> to, указывающую, что если я знаю и dimensions, и from, я могу однозначно определить to.

Далее, базовый случай: когда dimentions - пустой список, функция просто ухудшается до id:

instance Reshape '[] [a] [a] where
    reshape = id

А теперь мясо: рекурсивный случай.

instance (KnownNat n, Reshape tail [a] [b]) => Reshape (n:tail) [a] [[b]] where
    reshape = chunksOf n . reshape @tail
        where n = fromInteger . natVal $ Proxy @n

Первый он делает рекурсивный вызов reshape @tail, чтобы отделить предыдущее измерение, а затем вычисляет результат этого, используя значение текущего измерения в качестве размера фрагмента.

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

Давайте проверим это:

λ reshape @ '[1] [1,2,3]          
[[1],[2],[3]]                     

λ reshape @ '[1,2] [1,2,3,4]        
[[[1,2]],[[3,4]]]                   

λ reshape @ '[2,3] [1..12]              
[[[1,2,3],[4,5,6]],[[7,8,9],[10,11,12]]]

λ reshape @ '[2,3,4] [1..24]                                                      
[[[[1,2,3,4],[5,6,7,8],[9,10,11,12]],[[13,14,15,16],[17,18,19,20],[21,22,23,24]]]]

---

Для справки, вот полная программа со всеми импортами и расширениями:

{-# LANGUAGE
    MultiParamTypeClasses, FunctionalDependencies, TypeApplications,
    ScopedTypeVariables, DataKinds, TypeOperators, KindSignatures,
    FlexibleInstances, FlexibleContexts, UndecidableInstances,
    AllowAmbiguousTypes
#-}

import Data.Proxy (Proxy(..))
import Data.List.Split (chunksOf)
import GHC.TypeLits (Nat, KnownNat, natVal)

class Reshape (dimensions :: [Nat]) from to | dimensions from -> to where
    reshape :: from -> to

instance Reshape '[] [a] [a] where
    reshape = id

instance (KnownNat n, Reshape tail [a] [b]) => Reshape (n:tail) [a] [[b]] where
    reshape = chunksOf n . reshape @tail
        where n = fromInteger . natVal $ Proxy @n

Answer 2

@ Ответ Федора Сойкина идеален по отношению к актуальному вопросу. За исключением небольшой проблемы с самим вопросом. Списки списков - это не то же самое, что массив. Это распространенное заблуждение, что Haskell не имеет массивов, и вы вынуждены иметь дело со списками, которые не могут быть далеки от истины.

Поскольку вопрос помечен array и есть сравнение с numpy, я хотел бы добавить правильный ответ, который обрабатывает эту ситуацию для многомерных массивов. В экосистеме Haskell имеется пара библиотек массивов, одна из которых massiv

A reshape функциональность, подобная numpy, может быть достигнута с помощью resize' функция:

λ> 1 ... (18 :: Int)
Array D Seq (Sz1 18)
  [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 ]
λ> resize' (Sz (3 :> 2 :. 3)) (1 ... (18 :: Int))
Array D Seq (Sz (3 :> 2 :. 3))
  [ [ [ 1, 2, 3 ]
    , [ 4, 5, 6 ]
    ]
  , [ [ 7, 8, 9 ]
    , [ 10, 11, 12 ]
    ]
  , [ [ 13, 14, 15 ]
    , [ 16, 17, 18 ]
    ]
  ]