功能队列类型

Question

我想在功能上代表一种队列数据结构,但我还没有真正得到任何结论.我看过拉链,但它们似乎不是正确的结构.

具体来说,我试图表示一系列延迟线(对于回音或混响等音频效果),所以需要的功能如下:

1. 将数据附加到前面
2. 删除最后一项(可以扔掉)

对于我的特殊用途,这两个操作将结合使用以保持队列的大小恒定,但这种约束不是基本的.我可以使用一个列表,但我认为必须有一些更清洁的东西.表示此类型的最佳方式是什么？

我正在使用F#,但欢迎使用任何语言.

Answer 1

通过功能我假设你的意思是一个不可变的队列？

如果您使用F#和.NET,例如:

• ImmutableQueue <>
• FSharpX.Collections.Queue <>

如果您想了解如何实现功能队列,我推荐Chris Okasaki的Purely Functional Data Structures.

Okasaki实现功能队列的第一种方式List<>之一是使用两个,一个是弹出的,一个是你推送的.当弹出列表为空时,推送队列被反转并成为弹出列表.

请记住,这在很多方面都是一个效率相当低的队列,但它也很简单:

type Queue<'T> = 'T list*'T list

let empty<'T> : Queue<'T> = [], []

let isEmpty ((f, r) : Queue<'T>) : bool =
  match f, r with
  | []    , []  -> true
  | _     , _   -> false

let headAndTail ((f, r) : Queue<'T>) : 'T*Queue<'T> =
  match f, r with
  | []    , []  -> failwith "Queue is empty"
  | v::vs , r   -> v, (vs, r)
  | _     , r   -> let v::vs = List.rev r in v, (vs, [])

let snoc ((f, r) : Queue<'T>) (v : 'T) : Queue<'T> = (f, v::r)

let fold (f : 'S -> 'T -> 'S) (s : 'S) (q : Queue<'T>) : 'S =
  let rec loop ss qq =
    if isEmpty qq then ss
    else
      let hh, tt = headAndTail qq
      loop (f ss hh) tt
  loop s q

let ofArray (vs : 'T []) : Queue<'T> = vs |> Array.fold snoc empty

[<EntryPoint>]
let main argv = 
  let q = [| 1..20 |] |> ofArray
  fold (fun _ v -> printfn "%A" v) () q
  0