haskell - 在 Haskell 中隐藏状态 - Lazyset

Question

我正在尝试在 Haskell 中构建一个数据结构，它允许在有序的无限列表中进行高效查找。

如果这是 Java，我会做这样的事情:

class LazySet<T> {

    private Iterator<T> source;
    private NavigableSet<T> set;

    public LazySet(Iterator<T> source){
         this.source = source;
         this.set = new TreeSet<T>() ;               
    }

    public boolean contains(T elem){
        // Fetch items from the source into the set until the element(or one greater than it)
        // has been found
        while (this.set.ceiling(elem) == null){
                if (this.source.hasNext()){
                    this.set.add(this.source.next());
                }else{
                    return false;
                }
        }
        return this.set.contains(elem);
    }    
}

现在虽然这个类显然有状态，但该状态纯粹是为了优化，不会影响类的用户。所以它可以以功能方式使用。

这个类的 Haskell 等价物将是有状态的。

大概是这样的:

type LazySet a = (Set a, [a])

member :: Ord a => LazySet a -> a -> (Bool, LazySet a)

这将迫使用户显式地传递 LazySet，这使得它更难使用。

有没有办法告诉haskell:是的，这个东西有状态，但把它当作没有？

Answer 1

不。如果您的函数是有状态的，Haskell 会强制您在类型中声明它。方式有很多，包括State , ST , 和 IO ，但您必须使用其中之一。

虽然乍一看似乎有些限制，但我认为这最终是一件好事。当您知道类型没有说谎时，可以更轻松地信任库代码。