head and tail on difference lists in Haskell, à la LYAH

Learn You a Haskell mentions difference lists (search for this term on that page), where a list l is represented not directly but as a function (l++). This allows more efficient concatenation on both left and right. Concatenation becomes function composition, and one can finally convert to a real list by ($[]). I was wondering what operations one can support efficiently on difference lists. For example, the equivalent of (:) for difference lists is

\x l -> (x:) . l

Can one efficiently implement head and tail for difference lists? Here is the obvious implementation:

headTailDifList :: ([a] -> [a]) -> (a, [a] -> [a])
headTailDifList dl = (head l, ((tail l)++))
    where
    l = dl []

For real lists, \l -> (head l, tail l) runs in constant time. What about this headTailDifList? Perhaps due to lazy evaluation only the first element of l will be evaluated?

  1. What does it even mean to ask if this runs in constant time, given that a difference list is a function and not an actual "value"?
  2. Does headTailDifList run in constant time?
  3. Is there some other constant-time implementation? Here's a candidate:

    headTailDifList dl = (head (dl []), tail.dl )
    

    However, the tail part does not throw an exception if dl is id (the empty difference list).

Answers


Edit: added more about the thunk.

Begin by looking just at the conversion from a difference list to a regular list. This operation alone takes only constant time, because no evaluation is required. The resulting list will exist as a thunk which will be structured something like this:

The base definition of (++) is right-associative and needs to step through the entire first argument before it can continue with the second argument. This matches perfectly with the nested structure produced by the difference list, as each (++) gets a single list chunk as its first argument. Furthermore, because (++) is a good list producer, the entire structure exists lazily. Although fully evaluating it takes O(n), evaluating just the head is O(k) where k=number of chunks.

Consider if a,b == []; c = [1..]. Then head would need to first check that a and b are empty before moving on to c and finding the first element. In the worst case head would traverse the entire structure before finding the empty list constructor. Practically this is a very rare case however, and even then it's not particularly harmful because encountering an empty chunk and moving on is a constant-time operation.

In general use, evaluating a difference list should differ from a regular list in time complexity by only a constant factor for equivalent operations.

Producing just the first element of a difference list doesn't require O(n) time, as can easily be demonstrated by using infinite lists:

*Dl Control.Monad Control.Applicative> head $ ($ []) $ toDl [1..] . toDl [4..]
1
(0.01 secs, 2110104 bytes)

*Dl Control.Monad Control.Applicative> fmap (head . ($ [])) $ headTailDifList (toDl [1..])
(1,2)
(0.00 secs, 2111064 bytes)

*Dl Control.Monad Control.Applicative> fmap (head . ($ [])) $ headTailDifList (toDl [1..] . toDl [3..] . toDl [] . toDl [5..])
(1,2)
(0.01 secs, 3105792 bytes)

-- create a difference list
toDl :: [a] -> ([a] -> [a])
toDl l = (l ++)

Need Your Help

How do I use regex to search ignoring certain characters with NSPredicate?

objective-c ios regex search nspredicate

In Hebrew, there are certain vowels that NSPredicate fails to ignore even when using the 'd' (diacritic insensitive) modifier in the predicate. I was told that the solution is to use regular expres...

How do I convert numpy NaN objects to SQL nulls?

python postgresql psycopg2

I have a Pandas dataframe that I'm inserting into an SQL database. I'm using Psycopg2 directly to talk to the database, not SQLAlchemy, so I can't use Pandas built in to_sql functions. Almost

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.