Эффективный Haskell, эквивалентный аргументу NumPy

Question

Существует ли стандартный Haskell, эквивалентный NumPy's argsort функционировать?

Я использую HMatrix и поэтому хотел бы функцию, совместимую с Vector R который является псевдонимом для Data.Vector.Storable.Vector Double, argSort ниже приведена функция, которую я сейчас использую:

{-# LANGUAGE NoImplicitPrelude #-}

module Main where

import qualified Data.List as L
import qualified Data.Vector as V
import qualified Data.Vector.Storable as VS
import           Prelude (($), Double, IO, Int, compare, print, snd)

a :: VS.Vector Double
a = VS.fromList [40.0, 20.0, 10.0, 11.0]

argSort :: VS.Vector Double -> V.Vector Int
argSort xs = V.fromList (L.map snd $ L.sortBy (\(x0, _) (x1, _) -> compare x0 x1) (L.zip (VS.toList xs) [0..]))

main :: IO ()
main = print $ argSort a -- yields [2,3,1,0]

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

Эта реализация не очень эффективна, поскольку она преобразует входной вектор в список, а результат обратно в вектор. Есть ли что-то подобное (но более эффективное) где-нибудь?

Обновить

У @leftaroundabout было хорошее решение. Это решение, которое я закончил с:

module LAUtil.Sorting
  ( IndexVector
  , argSort
  )
  where

import           Control.Monad
import           Control.Monad.ST
import           Data.Ord
import qualified Data.Vector.Algorithms.Intro as VAI
import qualified Data.Vector.Storable as VS
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import           Numeric.LinearAlgebra

type IndexVector = VU.Vector Int

argSort :: Vector R -> IndexVector
argSort xs = runST $ do
    let l = VS.length xs
    t0 <- VUM.new l
    forM_ [0..l - 1] $
        \i -> VUM.unsafeWrite t0 i (i, (VS.!) xs i)
    VAI.sortBy (comparing snd) t0
    t1 <- VUM.new l
    forM_ [0..l - 1] $
        \i -> VUM.unsafeRead t0 i >>= \(x, _) -> VUM.unsafeWrite t1 i x
    VU.freeze t1

Это более удобно для использования с Numeric.LinearAlgebra поскольку вектор данных является Storable, Это использует распакованный вектор для индексов.

Answer 1

Используйте векторные алгоритмы:

import Data.Ord (comparing)

import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Algorithms.Intro as VAlgo

argSort :: (Ord a, VU.Unbox a) => VU.Vector a -> VU.Vector Int
argSort xs = VU.map fst $ VU.create $ do
    xsi <- VU.thaw $ VU.indexed xs
    VAlgo.sortBy (comparing snd) xsi
    return xsi

Обратите внимание, что это Unboxed скорее, чем Storable векторы. Последние должны сделать некоторые компромиссы, чтобы позволить нечистые операции C FFI и не могут должным образом обрабатывать гетерогенные кортежи. Вы можете, конечно, всегда convert в и из хранимых векторов.

Answer 2

Что лучше для меня, так это использование Data.map, так как он может быть объединен со списком и ускорился. Здесь n= длина хс.

import Data.Map as M (toList, fromList, toAscList)

    out :: Int -> [Double] -> [Int]
    out n !xs = let !a=  (M.toAscList (M.fromList $! (zip xs [0..n])))
                    !res=a `seq` L.map snd a
                in res

Однако это применимо только для периодических списков, как:

out 12 [1,2,3,4,1,2,3,4,1,2,3,4] == out 12 [1,2,3,4,1,3,2,4,1,2,3,4]