Haskell:从后面访问列表 [英] Haskell: accessing lists from back

问题描述

今天我开始学习 Haskell.我是函数式语言的新手，我很喜欢 Haskell.

然而，我有一个关于它的设计的问题，这让我很烦恼:从我目前的理解来看，访问列表后面的元素比访问前面的元素要复杂得多(某事像 xs:x 其中 xs::[a] 和 x::a 似乎不可能).

(据我所知)可以将一个列表附加到另一个列表(xs++[a])，但在运行时会花费更多(它需要遍历整个列表)并且不能用于模式匹配.

为什么 Haskell 缺少这样的操作?

解决方案

列表数据类型

data [a] = [] |一个:[一个]

的定义同上.只有两种模式可以匹配:[] 和 x : xs，其中 x 是头部，xs是尾巴.

准备一个列表

a = 1 : 2 : []b = 0 : a

<前>(:) <-- b/\0 (:) <--/\1 (:)/\2 []

只需添加一个新的 cons 单元并重用原始列表作为尾部.

但是，请记住 Haskell 数据结构是不可变的.附加到列表的尾部

a = 1 : 2 : []b = a ++ [3]

<前>(:) <-- a (:) <-- b/\/\1 (:) 1 (:)/\/\2 [] 2 (:)/\3 []

需要构建一个全新的列表，因为原始结构的任何部分都不能重用.

事实上，考虑

a = 0 : ab = 0 : [ x+1 |x <- b ]

<前>(:) <-- a (:) <-- b/\/\0 (:) <-- a 0 (:) <-- [ x+1 |x <- b ]/\/\0 (:) <-- a 1 (:) <-- [ x+1 |x <- [ x+1 |x <- b ] ]……

你将如何获得列表的最后一个元素，或者追加到最后?

还有其他数据结构，例如 dequeue 更适合前端和基于后台的访问.

Today I started learning Haskell. I'm kind of new with functional languages, and I'm enjoying Haskell a lot.

However I've got a question about its design which is bugging me: from what I understood so far it looks like accessing an element to the back of a list is a lot more complicated that accessing the element to the front (something like xs:x where xs::[a] and x::a doesn't seem to be possible).

(From what I understood) it's possible to append a list to another one (xs++[a]), but it'll cost more at run time (it requires to traverse the whole list) and it cannot be used for pattern matching.

Why is Haskell missing such operation?

解决方案

The list datatype

data [a] = [] | a : [a]

is defined like above. There's only two patterns you can match: [] and x : xs, where x is the head and xs is the tail.

Prepending to a list

a = 1 : 2 : []
b = 0 : a

 (:) <-- b
 / \  
0  (:)  <-- a
   / \
  1  (:)
     / \
    2   []

simply adds a new cons cell and reuses the original list as the tail.

However, keep in mind that Haskell data structures are immutable. Appending to the tail of a list

a = 1 : 2 : []
b = a ++ [3]

 (:) <-- a      (:) <-- b
 / \            / \
1  (:)         1  (:)
   / \            / \
  2   []         2  (:)
                    / \
                   3   []

requires building an entirely new list, because no part of the original structure can be reused.

In fact, consider

a = 0 : a
b = 0 : [ x+1 | x <- b ]

 (:) <-- a         (:) <-- b
 / \               / \
0  (:) <-- a      0  (:) <-- [ x+1 | x <- b ]
   / \               / \
  0  (:) <-- a      1  (:) <-- [ x+1 | x <- [ x+1 | x <- b ] ]
     ...               ...

How would you ever get the last element of the list, or append to the end?

There are other data structures such as dequeues which are more suited for both front- and back-based access.

这篇关于Haskell:从后面访问列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！