-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | A collection of Oleg Kiselyov's Haskell modules -- -- A collection of Oleg Kiselyov's Haskell modules (released with his -- permission) @package liboleg @version 0.1 -- | The final view to the typed sprintf and sscanf -- -- http://okmij.org/ftp/typed-formatting/FPrintScan.html -- -- This code defines a simple domain-specific language of string patterns -- and demonstrates two interpreters of the language: for building -- strings (sprintf) and parsing strings (sscanf). This code thus solves -- the problem of typed printf/scanf sharing the same format string posed -- by Chung-chieh Shan. This code presents scanf/printf interpreters in -- the final style; it is thus the dual of the code in PrintScan.hs -- -- Version: The current version is 1.1, Sep 2, 2008. -- -- References -- -- module Text.PrintScanF class FormattingSpec repr lit :: (FormattingSpec repr) => String -> repr a a int :: (FormattingSpec repr) => repr a (Int -> a) char :: (FormattingSpec repr) => repr a (Char -> a) fpp :: (FormattingSpec repr) => PrinterParser b -> repr a (b -> a) (^) :: (FormattingSpec repr) => repr b c -> repr a b -> repr a c data PrinterParser a PrinterParser :: (a -> String) -> (String -> Maybe (a, String)) -> PrinterParser a fmt :: (FormattingSpec repr, Show b, Read b) => b -> repr a (b -> a) newtype FPr a b FPr :: ((String -> a) -> b) -> FPr a b newtype FSc a b FSc :: (String -> b -> Maybe (a, String)) -> FSc a b sprintf :: FPr String b -> b sscanf :: String -> FSc a b -> b -> Maybe a showread :: (Show a, Read a) => PrinterParser a prefix :: String -> String -> Maybe String instance FormattingSpec FSc instance FormattingSpec FPr -- | http://okmij.org/ftp/typed-formatting/FPrintScan.html -- -- The initial view to the typed sprintf and sscanf This code defines a -- simple domain-specific language of string patterns and demonstrates -- two interpreters of the language: for building strings (sprintf) and -- parsing strings (sscanf). This code thus solves the problem of typed -- printf/scanf sharing the same format string posed by Chung-chieh Shan. -- -- Version: The current version is 1.1, Aug 31, 2008. -- -- References -- -- module Text.PrintScan data F a b FLit :: String -> F a a FInt :: F a (Int -> a) FChr :: F a (Char -> a) FPP :: PrinterParser b -> F a (b -> a) (:^) :: F b c -> F a b -> F a c -- | Printerparsers (injectionprojection pairs) data PrinterParser a PrinterParser :: (a -> String) -> (String -> Maybe (a, String)) -> PrinterParser a -- | a bit of syntactic sugar to avoid hitting the Shift key too many a -- time fmt :: (Show b, Read b) => b -> F a (b -> a) -- | The interpreter for printf It implements Asai's accumulator-less -- alternative to Danvy's functional unparsing intp :: F a b -> (String -> a) -> b -- | The interpreter for scanf ints :: F a b -> String -> b -> Maybe (a, String) sprintf :: F String b -> b sscanf :: String -> F a b -> b -> Maybe a -- | The format specification is first-class. One can build format -- specification incrementally This is not the case with OCaml's -- printf/scanf (where the format specification has a weird typing and is -- not first class). -- -- Primitive Printer/parsers showread :: (Show a, Read a) => PrinterParser a -- | A better prefixOf function prefix patt str --> Just str' if the -- String patt is the prefix of String str. The result str' is str with -- patt removed Otherwise, the result is Nothing prefix :: String -> String -> Maybe String -- | Haskell98 -- -- http://okmij.org/ftp/Algorithms.html#pure-cyclic-list -- -- Pure functional, mutation-free, constant-time-access double-linked -- lists -- -- Note that insertions, deletions, lookups have a worst-case complexity -- of O(min(n,W)), where W is either 32 or 64 (depending on the -- paltform). That means the access time is bounded by a small constant -- (32 or 64). -- -- Pure functional, mutation-free, efficient double-linked lists -- -- It is always an interesting challenge to write a pure functional and -- efficient implementation of an imperative algorithm destructively -- operating a data structure. The functional implementation has a -- significant benefit of equational reasoning and modularity. We can -- comprehend the algorithm without keeping the implicit global state in -- mind. The mutation-free, functional realization has practical -- benefits: the ease of adding checkpointing, undo and redo. The absence -- of mutations makes the code multi-threading-safe and helps in porting -- to distributed or non-shared-memory parallel architectures. On the -- other hand, an imperative implementation has the advantage of -- optimality: mutating a component in a complex data structure is a -- constant-time operation, at least on conventional architectures. -- Imperative code makes sharing explicit, and so permits efficient -- implementation of cyclic data structures. -- -- We show a simple example of achieving all the benefits of an -- imperative data structure -- including sharing and the efficiency of -- updates -- in a pure functional program. Our data structure is a -- doubly-linked, possibly cyclic list, with the standard operations of -- adding, deleting and updating elements; traversing the list in both -- directions; iterating over the list, with cycle detection. The code: -- --  uniformly handles both cyclic and terminated lists;  does not -- rebuild the whole list on updates;  updates the value in the current -- node in time bound by a small constant;  does not use or mention any -- monads;  does not use any IORef, STRef, TVars, or any other -- destructive updates;  permits the logging, undoing and redoing of -- updates, checkpointing;  easily generalizes to two-dimensional -- meshes. -- -- The algorithm is essentially imperative, thus permitting identity -- checking and in-place updates, but implemented purely -- functionally. Although the code uses many local, type safe -- heaps, there is emphatically no global heap and no global -- state. -- -- Version: The current version is 1.2, Jan 7, 2009. -- -- References -- -- Haskell-Cafe discussion ``Updating doubly linked lists''. January 2009 module Data.FDList -- | Representation of the double-linked list type Ref = Int data Node a Node :: a -> Ref -> Ref -> Node a node_val :: Node a -> a node_left :: Node a -> Ref node_right :: Node a -> Ref -- | Because DList contains the pointer to the current element, -- DList is also a Zipper data DList a DList :: Ref -> Ref -> IntMap (Node a) -> DList a dl_counter :: DList a -> Ref dl_current :: DList a -> Ref dl_mem :: DList a -> IntMap (Node a) -- | Operations on the DList a empty :: DList a -- | In a well-formed list, dl_current must point to a valid node All -- operations below preserve well-formedness well_formed :: DList a -> Bool is_empty :: DList a -> Bool -- | auxiliary function get_curr_node :: DList a -> Node a -- | The insert operation below makes a cyclic list The other operations -- don't care Insert to the right of the current element, if any Return -- the DL where the inserted node is the current one insert_right :: a -> DList a -> DList a -- | Delete the current element from a non-empty list We can handle both -- cyclic and terminated lists The right node becomes the current node. -- If the right node does not exists, the left node becomes current delete :: DList a -> DList a get_curr :: DList a -> a move_right :: DList a -> Maybe (DList a) -- | If no right, just stay inplace move_right' :: DList a -> DList a move_left :: DList a -> Maybe (DList a) -- | If no left, just stay inplace move_left' :: DList a -> DList a fromList :: [a] -> DList a -- | The following does not anticipate cycles (deliberately) takeDL :: Int -> DList a -> [a] -- | Reverse taking: we move left takeDLrev :: Int -> DList a -> [a] -- | Update the current node inplace update :: a -> DList a -> DList a -- | This one watches for a cycle and terminates when it detects one toList :: DList a -> [a]