Source code for list1

#!/usr/bin/python3
# -*- coding: utf-8 -*-

"""
:mod:`list1` module

:author: ̀FIL - IEEA - Univ. Lille1.fr <http://portail.fil.univ-lille1.fr>`_

:date: 2015, october

Provides constructor, selectors and modifiers for non mutable lists.

Lists are either empty, either essentially objects with two fields :

#. a *head* field which represent the head value  of the list,
#. and a *tail* field which is represent the tail of the list

"""

from collections import namedtuple

__List = namedtuple ('List',['head','tail'])


[docs]class ListEmptyError (Exception): """ Exception for empty lists """ def __init__ (self,msg): self.message = msg
[docs]def empty_list (): """ :return: an empty list :rtype: list :UC: none """ return None
[docs]def cons (x,l): """ :param x: :type x: any :param l: :type l: list :return: a new list with head x, and tail l :rtype: list :UC: l must be a list """ assert is_list (l), 'l must be a list' return __List (head=x,tail=l)
[docs]def tail (l): """ :param l: :type l: list :return: the tail of list l :rtype: list :UC: l must be non empty """ try: return l.tail except AttributeError: raise ListEmptyError ('list has no tail')
[docs]def is_empty (l): """ :param l: :return: - True if l is empty - False otherwise :rtype: bool :UC: none """ return l == empty_list ()
[docs]def is_list (x): """ :param x: object to test :type x: any :return: - True if x is a list - False otherwise :rtype: bool :UC: none """ return (x == empty_list () or (type (x) == type (cons (1,empty_list())))) ########################## # Non primitive operations ##########################
[docs]def length (l): """ :param l: :type l: list :return: the length of l :rtype: int :UC: none """ if is_empty (l): return 0 else: return 1 + length (tail (l))
def __reverse_aux (l1,l2): if is_empty (l1): return l2 else: return __reverse_aux (tail (l1), cons (head (l1),l2))
[docs]def reverse (l): """ :param l: :type l: list :return: a new list with elements of l in reverse order :rtype: list :UC: none """ return __reverse_aux (l,empty_list())
def __concat_aux (l1,l2): if is_empty (l1): return l2 else: return __concat_aux (tail (l1), cons (head (l1),l2))
[docs]def concat (l1,l2): """ :param l1: :type l1: list :param l2: :type l2: list :return: a new list obtained by concatenation of l1 and l2 :rtype: list :UC: none """ return __concat_aux (reverse (l1), l2)
if __name__ == '__main__': pass