Hide fortune in Haskell - Laziset

Question

I am trying to create a datastructure in Haskell, which allows me to efficiently search in an ordered endless list.

If it was Java, I would do something like this:

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);
    }    
}

Now that this class explicitly has a state, this state is purely for optimization and does not affect the user of the class. Thus, it can be used in a functional manner.

the Haskell equivalent of this class will consist of state.

Maybe something like this:

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

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

And this will make the user explicitly skip LazySet, which greatly complicates its use.

Is there a way to say haskell: Yes, this thing has a state, but treat it as if it weren’t?

Answer 1

. , Haskell . , State, ST IO, .

, , . , , .

Answer 2

XY.

import Data.List ( unfoldr )
import Control.Arrow ( (***) )
import qualified Data.List.Ordered as O

  (\ chunks -> [ (head chunk, to_balanced_tree nlevels chunk) 
                 | (nlevels, chunk) <- chunks] )
  . unfoldr (\ (xs,n) -> case xs of [] -> Nothing;
        _ -> Just ( (,) n *** flip (,) (n+1) $ splitAt (2^n-1) xs)
  . flip (,) 2
  . O.nub

– , , , .

() . ( data Tree a = Leaf | Node (Tree a) a (Tree a)) ( ) .

, , (, ), - Haskell.

( ), O.nub O (1) , . , , contains , .

Data.List.Ordered data-ordlist.

Answer 3

, . , , , .

---

You can do this with memo-trie. Basically, the trick is to replace the type set of the mutable structure with a static structure, which then can simply use Haskell's usual laziness. The important thing about the static structure is to have a sequence of increasingly large adjustments.

import Data.List (partition)

data PTrie a = SPTrie a :∧∧: PTrie a
data SPTrie a = NIT | Leaf a | SPTrie a :∧: SPTrie a

fromList :: [(Int, a)] -> PTrie a
fromList = go 0 1
 where go i₀ nC l = chunk :∧∧: go (i₀+nC) (nC*2) rest
        where (chunkSrc, rest) = partition ((<i₀+nC) . fst) l
              chunk = goS i₀ nC chunkSrc
       goS _ _ [] = NIT
       goS _ 1 ((_,k):_) = Leaf k
       goS i₀ nC l = goS i₀ nC' lChunk :∧: goS (i₀+nC') nC' rChunk
        where nC' = nC`quot`2
              (lChunk, rChunk) = partition ((<i₀+nC') . fst) l

llookup :: Int -> PTrie a -> Maybe a
llookup = go 1
 where go nC i (chunk :∧∧: rest)
        | i < nC     = goS nC i chunk
        | otherwise  = go (nC*2) (i-nC) rest
       goS _ _ NIT = Nothing
       goS _ _ (Leaf a) = Just a
       goS nC i (lChunk:∧:rChunk)
        | i<nC'      = goS nC' i lChunk
        | otherwise  = goS nC' (i-nC') rChunk
        where nC' = nC`quot`2