arrays - Haskell - 重现 numpy 的 reshape

Question

进入 Haskell，我试图重现 numpy's reshape 之类的东西与列表。具体来说，给定一个平面列表，将其 reshape 为一个 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

但是，无论我怎么做，我总是从编译器那里得到一个类型错误。据我了解，问题是在某些时候， acc 的类型推断为 id即 a -> a ，并且它不喜欢折叠中的函数列表都具有不同(尽管与组合兼容)类型签名的事实。我遇到了同样的问题，试图自己用递归而不是折叠来实现它。
这让我很困惑，因为我原本打算使用 [b]在 reshape的类型签名作为“另一个分离的类型”的替代，可以是 [[a]] 中的任何内容至 [[[[[a]]]]] .

我怎么错了？有没有办法真正实现我想要的行为，或者首先想要这种“动态”行为是完全错误的？

Answer 1

这里有两个细节与 Python 有本质上的不同，最终源于动态与静态类型。

第一个您已经注意到自己:在每个分 block 步骤中，结果类型都与输入类型不同。这意味着您不能使用 foldr ，因为它需要一个特定类型的函数。你可以通过递归来做到这一点。

第二题不太明显:reshape 的返回类型函数取决于第一个参数是什么。比如，如果第一个参数是 [2] ，返回类型为 [[a]] , 但如果第一个参数是 [2, 3] ，则返回类型为 [[[a]]] .在 Haskell 中，所有类型在编译时都必须是已知的。这意味着您的 reshape函数不能采用在运行时定义的第一个参数。换句话说，第一个参数必须在类型级别。

类型级别的值可以通过类型函数(又名“类型族”)计算，但因为它不仅仅是类型(即你也有一个值要计算)，所以自然(或唯一？)机制是类型类(class)。

所以，首先让我们定义我们的类型类:

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分 block 前一个维度，然后使用当前维度的值作为 block 大小来分 block 结果。

另请注意，我使用的是 chunksOf function from the library 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