Skip to content

Port Seq from Haskell to MoonBit #135

@illusory0x0

Description

@illusory0x0

简介

Finger Tree 是一种基于 2-3 树的函数式数据结构,通过在序列两端提供“手指”实现高效操作,同时支持序列的快速连接、分割和随机访问。

任务内容

移植 Haskell 语言中的 Seq 到 MoonBit, 实现 Data.equence 的大部分接口,并对每个接口,都提供黑盒测试, 在 README.mbt.md 中提供使用示例。

参考资料

下面两个文章提供如何在 MoonBit 编码 Polymorphic Recursion 的思路。

Learning Free Monad by FreeMaybe - 猗露的文章 - 知乎

Polymorphic Recursion in MoonBit - 猗露的文章 - 知乎

finger_tree.mbt 提供了 Finger Tree 的 MoonBit 基本实现,提供 cons, snoc, concat 这些核心功能。
剩下未实现的有

  • lazy sphine 这部分推荐使用 CAIMEOX/lazy 这个库, 用于实现均摊操作
  • split, index 推荐看论文 Finger trees: a simple general-purpose data structure
  • MoonBit 不支持 type famlilies 和 multi param type class. 所以 Measured typeclass 不需要实现,直接用 Int 作为 finger tree size(Measured) 然后 Monoid 操作用 +

产出

  1. 将仓库开源,并发布到 mooncakes,提供完整的文档、示例和测试,确保工具可用性和稳定性。

在本 issue 下回复仓库开源链接。

  1. Algorithms-Moonbit 提 PR, 将该库加入到集合中.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

Status

Done

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions