nested list in F#

Question

I am not sure if this is a stupid question, but I was doing some simple problems on lists in F#. I am unable to handle nested lists. My question is, Why I can't pass a nested list when I have declared a list as parameter of a function? I mean the nested list is also a list. What is the advantage of differentiating lists of simple int or char from lists of lists?

Answer 1

If a function is generic and takes a parameter 'a list, the type of 'a could also be a list. So the function would work with lists, or lists of lists, or lists of lists of lists, ...so long as the outer type is a list, 'a could be anything.

For example:

let isNonEmpty = function
    | [] -> false
    | _::_ -> true

isNonEmpty [1; 2; 3]
isNonEmpty [[1]; [2]; [3]]

If your function doesn't depend on the list elements being of a certain type it should probably be generic. If you post your code perhaps someone can help with that.

EDIT

A naive version of your flatten function, without using built-in functions, might be:

let flatten lst =
    let rec helper = function
        | [] -> []
        | h::tl ->
            match h with
            | Elem x -> x::helper tl
            | List xs -> helper xs @ helper tl
    helper [lst]

Answer 2

If you have a function requiring a list<char> and you have a list<list<char>> those types don't match. However, there is a function List.concat which will "flatten" the list of lists.

So:

let list = [ ['a'] ; ['b'] ]
let list' = list |> List.concat  // [ 'a' ; 'b' ]

Answer 3

For anyone who is looking for more of a dynamically typed nested list behavior, you should take a look at my NestedPair module:

https://gist.github.com/calebh/45871d3d40dc93526b3fd227cd577467

This module allows for "lists" of arbitrary depth by using a simple wrapper type.