說我有一個列表和一個矢量，我想將它們壓縮在一起。一個簡單的解決方案是將矢量轉換爲列表，並將兩個列表壓縮在一起。但是，這需要對矢量進行兩次遍歷（並且還要將內存分配轉換爲列表），其中一個將矢量轉換爲列表，另一個將矢量與另一個列表一起壓縮。將列表和矢量一起壓縮而不用重複遍歷
有沒有辦法在一個遍歷中一起壓縮？我想這需要某種狀態保持拉鍊（我猜它會保持向量索引的狀態，因爲它可以在O（1）時間索引）。
僞代碼：
let l1 = [1..10] :: [CInt]
let v1 = Data.Vector.Storable.fromList l1
map (\(x,y) -> x + y) (zipListVector l1 v1) -- zipListVector function is what I am after
融合確實踢在了這裏。
給出的下列程序：生成
import Data.Vector
import Prelude hiding (zip)
zipMe :: [a] -> Vector b -> Vector (a, b)
zipMe xs ys = zip (fromList xs) ys
以下核心：
Foo.$wzipMe
:: forall a_auS b_auT.
[a_auS]
-> GHC.Prim.Int#
-> GHC.Prim.Int#
-> GHC.Prim.Array# b_auT
-> Data.Vector.Vector (a_auS, b_auT)
[GblId,
Arity=4,
Str=DmdType LLLL,
Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=4, Value=True,
ConLike=True, Cheap=True, Expandable=True,
Guidance=IF_ARGS [0 0 0 0] 302 0}]
Foo.$wzipMe =
\ (@ a_auS)
(@ b_auT)
(w_sW7 :: [a_auS])
(ww_sWa :: GHC.Prim.Int#)
(ww1_sWb :: GHC.Prim.Int#)
(ww2_sWc :: GHC.Prim.Array# b_auT) ->
GHC.ST.runSTRep
@ (Data.Vector.Vector (a_auS, b_auT))
(\ (@ s_aBU) (s_aBV :: GHC.Prim.State# s_aBU) ->
case GHC.Prim.newArray#
@ (a_auS, b_auT)
@ (Control.Monad.Primitive.PrimState (GHC.ST.ST s_aBU))
ww1_sWb
(Data.Vector.Mutable.uninitialised @ (a_auS, b_auT))
(s_aBV
`cast` (GHC.Prim.State#
(Sym (Control.Monad.Primitive.TFCo:R:PrimStateST <s_aBU>))
:: GHC.Prim.State# (Control.Monad.Primitive.R:PrimStateST s_aBU)
~
GHC.Prim.State#
(Control.Monad.Primitive.PrimState (GHC.ST.ST s_aBU))))
of _ { (# s'#_aSF, arr#_aSG #) ->
letrec {
$s$wa_sX0 [Occ=LoopBreaker]
:: GHC.Prim.Int#
-> [a_auS]
-> GHC.Prim.Int#
-> GHC.Prim.State# (Control.Monad.Primitive.R:PrimStateST s_aBU)
-> (# GHC.Prim.State# s_aBU, GHC.Types.Int #)
[LclId, Arity=4, Str=DmdType LLLL]
$s$wa_sX0 =
\ (sc_sWB :: GHC.Prim.Int#)
(sc1_sWC :: [a_auS])
(sc2_sWD :: GHC.Prim.Int#)
(sc3_sWE
:: GHC.Prim.State#
(Control.Monad.Primitive.R:PrimStateST s_aBU)) ->
case sc1_sWC of _ {
[] -> (# sc3_sWE, GHC.Types.I# sc_sWB #);
: x_aGx xs1_aGy ->
case GHC.Prim.indexArray#
@ b_auT ww2_sWc (GHC.Prim.+# ww_sWa sc2_sWD)
of _ { (# x1_sWp #) ->
case GHC.Prim.>=# sc2_sWD ww1_sWb of _ {
GHC.Types.False ->
$s$wa_sX0
(GHC.Prim.+# sc_sWB 1)
xs1_aGy
(GHC.Prim.+# sc2_sWD 1)
((GHC.Prim.writeArray#
@ (Control.Monad.Primitive.PrimState (GHC.ST.ST s_aBU))
@ (a_auS, b_auT)
arr#_aSG
sc_sWB
(x_aGx, x1_sWp)
(sc3_sWE
`cast` (GHC.Prim.State#
(Sym (Control.Monad.Primitive.TFCo:R:PrimStateST <s_aBU>))
:: GHC.Prim.State#
(Control.Monad.Primitive.R:PrimStateST s_aBU)
~
GHC.Prim.State#
(Control.Monad.Primitive.PrimState (GHC.ST.ST s_aBU)))))
`cast` (GHC.Prim.State#
(Control.Monad.Primitive.TFCo:R:PrimStateST <s_aBU>)
:: GHC.Prim.State#
(Control.Monad.Primitive.PrimState (GHC.ST.ST s_aBU))
~
GHC.Prim.State#
(Control.Monad.Primitive.R:PrimStateST s_aBU)));
GHC.Types.True -> (# sc3_sWE, GHC.Types.I# sc_sWB #)
}
}
}; } in
case $s$wa_sX0
0
w_sW7
0
(s'#_aSF
`cast` (GHC.Prim.State#
(Control.Monad.Primitive.TFCo:R:PrimStateST <s_aBU>)
:: GHC.Prim.State#
(Control.Monad.Primitive.PrimState (GHC.ST.ST s_aBU))
~
GHC.Prim.State# (Control.Monad.Primitive.R:PrimStateST s_aBU)))
of _ { (# new_s1_aDv, r1_aDw #) ->
case r1_aDw of _ { GHC.Types.I# tpl1_aU1 ->
case GHC.Prim.unsafeFreezeArray#
@ (Control.Monad.Primitive.PrimState (GHC.ST.ST s_aBU))
@ (a_auS, b_auT)
arr#_aSG
(new_s1_aDv
`cast` (GHC.Prim.State#
(Sym (Control.Monad.Primitive.TFCo:R:PrimStateST <s_aBU>))
:: GHC.Prim.State# (Control.Monad.Primitive.R:PrimStateST s_aBU)
~
GHC.Prim.State#
(Control.Monad.Primitive.PrimState (GHC.ST.ST s_aBU))))
of _ { (# s'#1_aV8, arr'#_aV9 #) ->
(# s'#1_aV8
`cast` (GHC.Prim.State#
(Control.Monad.Primitive.TFCo:R:PrimStateST <s_aBU>)
:: GHC.Prim.State#
(Control.Monad.Primitive.PrimState (GHC.ST.ST s_aBU))
~
GHC.Prim.State# (Control.Monad.Primitive.R:PrimStateST s_aBU)),
Data.Vector.Vector @ (a_auS, b_auT) 0 tpl1_aU1 arr'#_aV9 #)
}
}
}
})
這確實只有一個分配，和熔斷器的那些環。 （我相信它利用了這個事實，即壓縮矢量的長度至多是最初的長度，並且分配了一個最初大的矢量。）
GHC似乎做了遍歷的巧妙優化將其轉換爲列表時向量一次。給予@Louis Wasserman的答案，並在這裏添加清除ghc-core - 我的代碼與Louis不同 - 我將它壓縮到一個列表中而不是一個向量中（更方便，因爲列表很小，不會經常生成）：
首先代碼：
module Foo where
import Data.Vector
import Prelude
zipMe :: [a] -> Vector b -> [(a,b)]
zipMe xs ys = Prelude.zip xs (toList ys)
如何獲得GHC芯（我用7.4.1）：ghc -O -fforce-recomp Foo.hs -ddump-simpl -dsuppress-all
盪滌GHC核心如下輸出：
--| this is called by zipMeHelper at loop termination
zipMe1 = \ _ -> []
--| Helper function called by zipMe - ys is converted into vector representation (start end array) - that is what I think. Correct me if I got the representation wrong
zipMeHelper =
\ xs start end array ->
letrec {
go =
\ index ->
case >=# index end of _ { --| is index >= end? (>=#) is prim version of >=
False -> --| note vector is being traversed here only once - vector element vecElem is: array at (start + index)
case indexArray# array (+# start index) of _ { (# vecElem #) ->
let { --| call a recursive function go2 if end of vector is not reached
go2 = go (+# index 1) } in
\ list -> --| take the list element and combine with vecElem
case list of _ {
[] -> [];
: x1 xs1 -> : (x1, vecElem) (go2 xs1)
}
};
True -> zipMe1 |-- if here, end of index was reached - terminate with []
}; } in
go 0 xs
|-- zipMe function from Foo.hs
zipMe =
\ xs ys ->
case ys of _ { Vector start end array ->
zipMeHelper xs start end array
}
「一個SIM卡ple解決方案是將矢量轉換爲列表，並將兩個列表壓縮在一起。「不要它們融合，導致一次遍歷矢量？ – dave4420 2012-02-10 15:27:25
@ dave4420，很好的問題。我不知道。如果融合開始了（即使數據類型從向量變爲列表 - 不確定是否存在該變換的融合規則），我可以使用簡單的解決方案。 – Sal 2012-02-10 15:48:29
'Data.Vector.Storable.toList'內聯到某個具有重寫規則的東西，而'zipWith'具有重寫規則，但我沒有仔細查看這些重寫規則是否可以協同工作以產生融合。我的（相對缺乏經驗的）思想似乎是合理的。 – dave4420 2012-02-10 16:21:39