Haskell中是否有索引列表,是好还是坏？

Question

我是Haskell世界的新来者,我想知道是否有这样的事情:

data IndexedList a = IList Int [a]

findIndex::(Int->Int)->IndexedList a->(a,IndexedList a)
findIndex f (IList x l) = (l!!(f x), IList (f x) l)

next::IndexedList a->(a,IndexedList a)
next x = findIndex (+1) x

我注意到这种列表不是纯函数,而是对某些应用程序有用.它应该被视为有害吗？

谢谢,

短发

Answer 1

拥有一个配有指向列表中特定位置的列表肯定是有用的.但是,它通常在Haskell中完成的方式有所不同 - 而不是使用显式指针,我们倾向于使用拉链.

列表拉链看起来像这样

data ListZipper a = LZ [a] a [a] deriving (Show)

您应该将中间字段a视为当前指向的元素,第一个字段[a]是当前位置之前的元素,最后一个字段[a]是当前位置之后的元素.

通常我们以相反的顺序将元素以相反的顺序存储在当前元素之前,以提高效率,以便[0, 1, 2, *3*, 4, 5, 6]具有指向中间元素的指针的列表将存储为

LZ [2,1,0] 3 [4,5,6]

您可以定义将指针向左或向右移动的函数

left  (LZ (a:as) b bs) = LZ as a (b:bs)
right (LZ as a (b:bs)) = LZ (a:as) b bs

如果你想向左或向右移动n,那么你可以借助于另一个函数的函数来做到这一点,并将它应用于它n的参数

times n f = (!!n) . iterate f

所以要向左移动三次,你可以使用

>> let lz = LZ [2,1,0] 3 [4,5,6]
>> (3 `times` left) lz
LZ [] 0 [1,2,3,4,5,6]

你的两个功能findIndex,并next可以写成

next :: ListZipper a -> (a, ListZipper a)
next = findIndex 1

findIndex :: Int -> ListZipper a -> (a, ListZipper a)
findIndex n x = let y@(LZ _ a _) = (n `times` right) x in (a, y)