Haskell - 重现 numpy 的重塑

Question

进入 Haskell，我试图用列表重现类似numpy 的 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

但是，无论我怎么做，我总是从编译器那里得到一个类型错误。根据我的理解，问题是在某些时候， for 的类型acc被推断为id's ie a -> a，并且它不喜欢折叠中的函数列表都具有不同（尽管与组合兼容）类型的事实签名。我遇到了同样的问题，试图用递归而不是折叠来实现它。这让我很困惑，因为最初我打算将[b]inreshape的类型签名作为“另一种分离类型”的替代品，它可以是从[[a]]到[[[[[a]]]]].

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

Answer 1

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

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

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

类型级别的值可以通过类型函数（又名“类型系列”）计算，但因为它不仅仅是类型（即您还有一个要计算的值），自然（或唯一？）机制是类型班级。

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

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

该类具有三个参数：dimensionsof kind[Nat]是类型级别的数字数组，表示所需的维度。from是参数类型，to是结果类型。请注意，即使知道参数类型始终为[a]，我们也必须在此处将其作为类型变量使用，否则我们的类实例将无法正确匹配a参数和结果之间的相同内容。

另外，这个类有一个函数依赖dimensions from -> to，表明如果我知道dimensions和from，我可以明确地确定to。

接下来，基本情况：whendimentions是一个空列表，函数只是降级为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

@Fyodor Soikin 的回答就实际问题而言是完美的。除了问题本身有一点问题。列表列表与数组不同。一种常见的误解是 Haskell 没有数组，而您被迫处理列表，这与事实相去甚远。

因为问题被标记为array并且与 进行了比较numpy，所以我想添加一个正确的答案来处理多维数组的这种情况。Haskell 生态系统中有几个数组库，其中之一是massiv

甲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 ]
    ]
  ]