CODEWITHSUNDEEP
listhaskell
Andre Proenza
Andre Proenza

Reputation: 149

Slice a list in haskell with specific indexes

I have this list:

[[0,4,1,4],[1,12,1,4],[2,8,1,4],[3,54,2,4],[4,1,2,2]]

I also have another list: [2,3] -- Represents the indexes i want to get from each sublist

Output should be like:

[[1,4],[1,4],[1,4],[2,4],[2,2]]

Another example:

List :

[[0,4,1,4],[1,12,1,4],[2,8,1,4],[3,54,2,4],[4,1,2,2]]

Indexes : [0,2,3]

Output should be like:

[[0,1,4],[1,1,4],[2,1,4],[3,2,4],[4,2,2]]

Upvotes: 3

Views: 336

Answers (2)

Iceland_jack
Iceland_jack

Reputation: 7014

If the elements are always 4-tuples consider using a specialized type for it (Linear.V4)

type V4 :: Type -> Type
data V4 a = V4 a a a a

along with an indexing type that gives total indexing, because we know V4 has a static size (this is because V4 is a Representable functor):

type Fin4 :: Type
data Fin4 = Fin0 | Fin1 | Fin2 | Fin3

infixl 9 !!!

(!!!) :: V4 a -> Fin4 -> a
V4 a _ _ _ !!! Fin0 = a
V4 _ a _ _ !!! Fin1 = a
V4 _ _ a _ !!! Fin2 = a
V4 _ _ _ a !!! Fin3 = a

This is enough to define slices using Willem's definition

slices :: [Fin4] -> [V4 a] -> [[a]]
slices is = map ((`map` is) . (!!!))

>> slices [Fin2, Fin3] example
[[1,4],[1,4],[1,4],[2,4],[2,2]]
>> slices [Fin0, Fin2, Fin3] example
[[0,1,4],[1,1,4],[2,1,4],[3,2,4],[4,2,2]]

This can be generalized for vectors of any length

type N :: Type
data N = O | S N

infixr 5 :>

type Vec :: N -> Type -> Type
data Vec n a where
 VNil :: Vec O a
 (:>) :: a -> Vec n a -> Vec (S n) a
deriving stock
 instance Show a => Show (Vec n a)
deriving stock
 instance Functor (Vec n)

type Fin :: N -> Type
data Fin n where
 FinO :: Fin (S n)
 FinS :: Fin n -> Fin (S n)

infixl 9 !!!

(!!!) :: Vec n a -> Fin n -> a
VNil    !!! fin      = case fin of
(a:>as) !!! FinO     = a
(a:>as) !!! FinS fin = as !!! fin

slices :: [Fin n] -> [Vec n a] -> [[a]]
slices = ..

example :: [Vec (S (S (S (S O)))) Int]
example =
 [ 0:>4:>1:>4:>VNil
 , 1:>12:>1:>4:>VNil
 , 2:>8:>1:>4:>VNil
 , 3:>54:>2:>4:>VNil
 , 4:>1:>2:>2:>VNil
 ]

Indices and lists of tuples can be generalized to work for any functor

slices :: Functor f => Functor g => f (Fin n) -> g (Vec n b) -> g (f b)
slices is = fmap ((`fmap` is) . (!!!))

If we treat the list of examples as an 5-ary vector

example :: Vec (S (S (S (S (S O))))) (Vec (S (S (S (S O)))) Int)
example
  = (0:>4:>1:>4:>VNil)
 :> (1:>12:>1:>4:>VNil)
 :> (2:>8:>1:>4:>VNil)
 :> (3:>54:>2:>4:>VNil)
 :> (4:>1:>2:>2:>VNil)
 :> VNil

>> slices (FinS (FinS FinO) :> FinS (FinS (FinS FinO)) :> VNil) example

   (1 :> 4 :> VNil)
:> (1 :> 4 :> VNil)
:> (1 :> 4 :> VNil)
:> (2 :> 4 :> VNil)
:> (2 :> 2 :> VNil)
:> VNil

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476584

You obtain the item in a list with a given index with (!!) :: [a] -> Int -> a, for example:

Prelude> [0,4,1,4] !! 0
0
Prelude> [0,4,1,4] !! 2
1
Prelude> [0,4,1,4] !! 3
4

We thus can perform a mapping to obtain the items for a list of items:

Prelude> map ([0,4,1,4] !!) [0,2,3]
[0,1,4]

we thus can slice a list of lists with:

slices :: [Int] -> [[a]] -> [[a]]
slices is = map ((`map` is) . (!!))

For example:

Prelude> slices [0,2,3] [[0,4,1,4],[1,12,1,4],[2,8,1,4],[3,54,2,4],[4,1,2,2]]
[[0,1,4],[1,1,4],[2,1,4],[3,2,4],[4,2,2]]

Using (!!) is however unsafe: it is not guaranteed that a list has an element with the given index, furthermore, it is not very efficient: it takes O(k) to obtain the k-th element. Therefore it is better to work with Vector or an Array and with lookups that return a Nothing when the index is out of range, for example for a Vector, we can use (!?) :: Vector a -> Int -> Maybe a.

Upvotes: 3

Related Questions