3
$\begingroup$

I like to have a list just like in Python, but for Fortran. I know that there is a generic list type. But here I would have to define a type for each data I would like into the list, e.g. one for Real*8, one for Complex*16,Dimension(:,:) and so on. I would like to put data into the list for which I do not have to define the dimension and if it is Real, Complex or Integer - just like a list in Python where I can put everything I want into it. Is that possible? Does such a list already exist for Fortran?

$\endgroup$
  • 1
    $\begingroup$ Since this is a pure programming question, it's better to ask it at stackoverflow.com. $\endgroup$ – Christian Clason Jun 2 '14 at 7:35
  • 3
    $\begingroup$ It's a question about a language used in computational science, so I'm on the fence about it. Given that we are turning away a fair number of package- and language-specific questions on the site, it's probably time to revamp the page on topicality. $\endgroup$ – Geoff Oxberry Jun 2 '14 at 21:23
4
$\begingroup$

Disclaimer: I am the author of the linked modules.

First I would recommend to post this question at Stackoverflow, many Fortran experts meet there.

There are more possible approaches to this problem. One similar to C void pointers (using transfer) or safer one using class(*). Both theoretically allow heterogeneous lists. You are then responsible to correctly retrieve the items of different types. In the class(*) case it is done safely using the select type construct.

Then there approaches using parametric polymorphism similar to C++ templates, but done using a preprocessor and include. They are IMHO simpler to use, but only items of one type can be in the copy of the list. You can make a separate copy for every type you need.

You can find example modules of both at https://github.com/LadaF/fortran-list . I do not claim it is perfect, but it suits my needs and I use it regularly.

----EDIT-----

If you don't like a linked list, because you require random access and you can live with more difficult appending and even more difficult inserting and deleting, use a Fortran array of this simple derives type:

module array_list

  type container
    class(*), allocatable :: item
    class(*), allocatable :: items(:)
  end type

  interface add_item
    module procedure add_item_scalar
    module procedure add_item_array
  end interface

contains

  subroutine add_item_scalar(a, e)
    type(container),allocatable,intent(inout) :: a(:)
    class(*),intent(in) :: e
    type(container),allocatable :: tmp(:)

      if (.not.allocated(a)) then
        allocate(a(1))
        allocate(a(1)%item, source = e)
      else
        call move_alloc(a,tmp)
        allocate(a(size(tmp)+1))
        a(1:size(tmp)) = tmp
        allocate(a(size(tmp)+1)%item, source = e)
      end if
   end subroutine

  subroutine add_item_array(a, e)
    type(container),allocatable,intent(inout) :: a(:)
    class(*),intent(in) :: e(:)
    type(container),allocatable :: tmp(:)

      if (.not.allocated(a)) then
        allocate(a(1))
        allocate(a(1)%items(size(e)), source = e)
      else
        call move_alloc(a,tmp)
        allocate(a(size(tmp)+1))
        a(1:size(tmp)) = tmp
        allocate(a(size(tmp)+1)%items(size(e)), source = e)
      end if
   end subroutine

end module



  use array_list

  type(container), allocatable :: a_list(:)

  type newtype
  end type

  integer i

  call add_item(a_list, 1)

  call add_item(a_list, 5.5)

  call add_item(a_list, (4., 5.))

  call add_item(a_list, newtype())

  call add_item(a_list, [1, 2, 3, 4, 5])

  do i = 1, size(a_list)
    call print(a_list(i))
  end do

contains

  subroutine print(c)
    type(container), intent(in) :: c

    if (allocated(c%item)) then
      select type (x=>c%item)
        type is (integer)
          print *, x
        type is (real)
          print *, x
        type is (complex)
          print *, x
        type is (newtype)
          print *, "is newtype"
        class default
          print *, "is unknown type"
      end select
    else if (allocated(c%items)) then
      select type (x=>c%items)
        type is (integer)
          print *, x
        type is (real)
          print *, x
        type is (complex)
          print *, x
        type is (newtype)
          print *, "is array of newtype"
        class default
          print *, "is array of unknown type"
      end select
    else
      write(*,*) "Error, empty container"
    end if
  end subroutine

end

compile and run

> sunf90 alist.f90 
> ./a.out 
 1
 5.5
 (4.0,5.0)
 is newtype
 1 2 3 4 5
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your implementation is a linked list. Python lists are implemented as arrays in C. Arrays are not linked lists; as I pointed out in my post, random access for an array is an $O(1)$ op, and random access for a linked list is an $O(n)$ op, because you may have to traverse the whole list (for a singly-linked list; for a doubly-linked list, you can reduce the worst case by a factor of 2). $\endgroup$ – Geoff Oxberry May 27 '14 at 21:07
  • $\begingroup$ Yes, OK, but I assume array of pointers. It is actually much easier to do that in Fortran. I will write it in a minute and add it to the answer. $\endgroup$ – Vladimir F May 27 '14 at 21:16
  • $\begingroup$ I meant easier than the linked list. Of course more features can be added if one has more than 15 minutes to write it and test it. $\endgroup$ – Vladimir F May 27 '14 at 21:35
  • $\begingroup$ This is cool. Compiling with ifort though will not work since some of the used features are not yet implemented (like source=item). Would it be possible to get it to work with ifort? $\endgroup$ – DaPhil May 28 '14 at 7:26
  • $\begingroup$ The current version also deals with arrays, but there is a bug with the arrays in gfortran-4.9 I will report to developers. It works well in Solaris Studio 12.4. It crashes in ifort 14 and I will report it. (The linked lists are tested with ifort regularly.) $\endgroup$ – Vladimir F May 28 '14 at 8:29
2
$\begingroup$

This answer is more of a comment; my remarks are too long for a comment and having additional formatting options will be useful.

I know that there is a generic list type.

A quick perusal of the link you cite describes a Fortran module for a linked list. Random access (that is, look up the element stored at an arbitrary index) of a list in Python is $O(1)$; for a linked list of length $n$, random access is $O(n)$, because to look at the $i$th element, you must start at the head of the list, and traverse $i - 1$ elements (the links of the list) to get to the $i$th element. The data structures are different.

I would like to put data into the list for which I do not have to define the dimension and if it is Real, Complex or Integer - just like a list in Python where I can put everything I want into it. Is that possible?

Yes. Fortran is a Turing-complete language, and what you're suggesting is emulating the features of Python (also a Turing-complete language), so it is possible to define a Fortran "list" data type.

One potential way of implementing a "list" data type would be to have three arrays:

  • the first array is essentially storage for data; you can use the transfer function to convert data into a common representation, like, say, an array of characters (this strategy more or less emulates C-style void pointers in Fortran, see this blog post)
  • the second array stores index offsets for each object you store in the list
  • the third array stores type information for each object in some manner; this step is probably easy for built-in types, but Fortran 90 allows you to define composite types (sort of like structs), and storing information for composite types might require a more involved scheme or more auxiliary data structures.

I'm not saying this sort of scheme is the best way -- it's probably not, since it's the first idea that popped into my head. I am biased against using pointers in Fortran, since I learned a Fortran 77-biased style of Fortran 90, but Fortran pointers could be used to great effect here. If I were implementing this in C, I would absolutely use pointers, because pointers are essential to the C idiom.

I would guess that most methods for emulating a "list" data type are going to involve clever data encoding and retrieval schemes, plus a nice interface to hide it away.

You might find looking at descriptions of the C implementation of the Python list data type like this blog post, or the source code, or the answers to this Stack Overflow question helpful.

Does such a list already exist for Fortran?

I couldn't find one with a quick search.

I like to have a list just like in Python, but for Fortran.

Why? What is your use case? If you know the type of data you want to store in advance, it's easier just to use arrays with known data types, and it will save you work, hassle, and probably execution time (storing arbitrary objects requires some indirection and additional memory references). Furthermore, it's more idiomatic Fortran to use standard array data structures (even though, yes, people can and do emulate other data structures using arrays); data structure munging is more characteristically done in other languages (C-style languages, interpreted languages like Lisp, Python, Ruby, etc.).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ FWIW, I implemented generic tree data structures in Fortran using TRANSFER and Fortran pointers. It works extremely well and was relatively simple. Everything is TRANSFER'd into a CHARACTER array. Unfortunately I can't share the code for it, but it can be done using the ideas on the blog post you linked. $\endgroup$ – tpg2114 May 25 '14 at 22:45
  • $\begingroup$ Sometimes it is easier, when you create unknown number of items, to first fill a list with them and then move them to a final array. $\endgroup$ – Vladimir F May 27 '14 at 14:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.