Combinatorial Problems in Haskell

A Simple Exercise

"Given three sets of characters, build all the possible words of 3 characters, with the first character from the first set, the second character from the second set, and the last character from the last set."

This is an exercise adapted from a similar one on the Haskell Programming from first principles book, and the results are part of the work done during the Haskell Day with my group of Haskellers!

{-# LANGUAGE OverloadedStrings #-}

module Combinatorial where


set1 :: [Char]
set1 = "ab"

set2 :: [Char]
set2 = "12"

set3 :: [Char]
set3 = set1

The Recursive Solution

In a classical imperative solution we would write three nested loops trying all combinations. In Haskell we can replace loops with recursion.

allWordsOf3Chars :: [Char] -> [Char] -> [Char] -> [String]
allWordsOf3Chars set1 set2 set3 = combine1 set1 set2 set3
 where

   combine1 [] _ _ = []
   combine1 (c1:cs) set2 set3 = combine2 c1 set2 set3 ++ combine1 cs set2 set3

   combine2 _ [] _ = []
   combine2 c1 (c2:cs) set3 = combine3 c1 c2 set3 ++ combine2 c1 cs set3

   combine3 _ _ [] = []
   combine3 c1 c2 (c3:cs) = [[c1, c2, c3]] ++ combine3 c1 c2 cs

We test it

test1 = allWordsOf3Chars set1 set2 set3

  > test1 
  ["a1a","a1b","a2a","a2b","b1a","b1b","b2a","b2b"]

The KISS Solution

In Haskell list comprehension has a combinatorial semantic, and so we can write simply

allWordsOf3Chars' set1 set2 set3
  = [ [c1, c2, c3] | c1 <- set1, c2 <- set2, c3 <- set3 ]

isOk1 = test1 == (allWordsOf3Chars' set1 set2 set3)

  > isOk1
  True

The KISS solution is very easy to read, and very fast to write. A good selling point for the Haskell language.

The Advanced Solution

In Haskell the Applicative instance of List, has a combinatorial semantic, so we can write

allWordsOf3Chars'' set1 set2 set3
  = (\c1 c2 c3 -> [c1, c2, c3] ) <$> set1 <*> set2 <*> set3

isOk2 = test1 == (allWordsOf3Chars'' set1 set2 set3)

  > isOk2
  True

The Extended Exercise

We can generalize the first problem, passing a list of sets of chars, instead of only 3 sets.

The Extended Recursive Solution

In an imperative language, generalizing the solution is not simple, because we have a number of loops that is not fixed.

Generalizing the Haskell recursive solution is apparently simpler, because we start already from a recursion, but in practice it is rather hard to figure out the right algorithm.

combineWords :: [String] -> [String]
combineWords sets = combine [] sets 

 where

   combine :: String -> [String] -> [String]
   combine decidedPart [] = [decidedPart]
   combine decidedPart (set1:sets) = choices decidedPart set1 sets 

   choices :: String -> String -> [String] -> [String]
   choices decidedPart currentSet otherSets =
     concatMap (\c -> combine (decidedPart ++ [c]) otherSets) currentSet

isOk3 = test1 == (combineWords [set1, set2, set3])

  > isOk3
  True

This algo works because:

• it has a main loop on each set
• the inner loop selecting one character from the set, calls again the main loop function for obtaining all the possible solutions with the remaining sets

It is a double recursion , and double recursion is often hard to understand.

Writing this algo required too much time respect the initial planned time, and I can not declare that writing it in Haskell is a very easy task.

The extended KISS Solution

Apparently the previous KISS solution based on list comprehension, can not be extended easily to the new version of the problem.

The Extended Advanced Solution

I were in a meetup, so I asked help to someone more knowledgeable than me, and his solution was shocking

combineWords''' :: [String] -> [String]
combineWords''' sets = sequence sets

isOk4 = test1 == (combineWords''' [set1, set2, set3])

  > isOk4
  True

I'm not completely sure of the reason this algo works. I need to study better Haskell, and the magic behind sequence.

  >:t sequence
  sequence :: (Traversable t, Monad m) => t (m a) -> m (t a)

In any case this solution shows the power of Haskell abstractions.

The Pragmatic Solution

At this point, I'm not completely satisfied from the Haskell language:

• the recursive solution is too time-consuming and difficult to obtain
• the advanced solution is very short, but too deep for my taste

Is there a better way for solving the problem?

We have a combinatorial problem. For sure an iconic language for expressing and solving combinatorial problems is Prolog. But Haskell supports very well Domain Specific Languages (DSL), and so I can use a Prolog-like DSL language also in Haskell. In this case the MonadPlus applied to lists, is the right instance to use. Note that in case of very complex combinatorial problems, the best solution is probably using high-performance packages like LogicGrowsOnTree, but in this case it is overkill.

combineWords'''' :: [String] -> [String]
combineWords'''' sets = combine [] sets
 where
   combine decidedPart [] = return decidedPart
   combine decidedPart (set1:sets) = do
     c <- set1
     combine (decidedPart ++ [c]) sets

isOk5 = test1 == combineWords'''' [set1, set2, set3]

  > isOk5
  True

Don't ask me why, but this version of the function was very fast and natural to write for me, and very readable. It is based on a simple constraint, and only one recursive call. Probably because a single recursion is easier to understand than the dual recursion version, and because I were accustomed to Prolog.

Also the MonadPlus version of the first version of the problem is very natural to write

allWordsOf3Chars'''' :: [Char] -> [Char] -> [Char] -> [String]
allWordsOf3Chars'''' set1 set2 set3 = do
  c1 <- set1
  c2 <- set2
  c3 <- set3
  return [c1, c2, c3]

isOk6 = test1 == allWordsOf3Chars'''' set1 set2 set3

  > isOk6
  True

Conclusions

If some problems are hard to solve in Haskell, probably there exists some DSL able to express and solve them in a more natural way. The advantage of studying a new DSL, it is that after the initial investment of time, all problems in the same domain can be solved faster.

Probably there is also a payoff in studying better Applicative, Traversable, and sequence function, but for this problem, the MonadPlus solution seems to me a good balance between simplicity and terseness of the code.

OSS Licenses Debugging

New Conclusions

After this discussion on one of the OSI mailing lists, now I think that MIT, BSD, and ISC are true permissive licences. As usual I'm not a lawyer, and there were no judicial deliberation, so take these notes at your own risk.

Suppose that:

• A is product released under MIT, BSD or ISC license
• B is a new/derived product using A source code, but released under different license terms
• BB is the author of B

From what I understood, if B product cite/credit A copyright holders, and A original license, then thanks to very permissive A license, B product can use A source code inside it. Then according Berne Convention, BB can release B under the license terms he prefers, because he is the copyright holder of a new/derived product B, and not a distributor of A.

Obviously these passages are only needed if BB wants to "release A" under a different license. Otherwise BB can simply add himself to the list of A contributors/copyright holders, and BB can be a normal distributor/contributor of A product.

I will maintain the old but incorrect post, because maybe it can be useful also to others having similar problems in interpreting these licenses. The source of the problem was in the interpretation of terms like "reproduce", "retain" that are to be considered like a citation/credit of the original product license, and not as an inclusion of the original license requirements also into the license of the new released product.

Old Post Content, with Logical Errors Inside

Abstract

Despite the common wisdom, many permissive licenses like BSD, MIT, ISC are not easy to understand and apply correctly, and theirs terms are ambiguous. Apache-2.0 license is instead a lot more clear and it should be favored.

BSD License

I had to release a short piece of code, using a simple and permissive OSS license. According Wikipedia

BSD licenses are a family of permissive free software licenses, imposing minimal restrictions on the redistribution of covered software.

In particular BSD can be used in commercial and in GPL software:

The BSD License allows proprietary use and allows the software released under the license to be incorporated into proprietary products. Works based on the material may be released under a proprietary license as closed source software, allowing usual commercial usages under.

Perfect!!

Then for sake of security I studied the license text, and I found that it is far from easy to understand!! This is the BSD-2 license template:

Copyright (c) <year>, <copyright holder>
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this
   list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
   this list of conditions and the following disclaimer in the documentation
   and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Suppose B is a product released under the BSD-2 license, and that there is a commercial product C including parts of B source code, and released in compiled form. The license of C can be something like

Copyright (c) 2016, Acme Inc.
All rights reserved.

You can use and distribute this software only if you own a 
valid commercial license from Acme Corporation Inc.

Is C respecting the BSD-2 license of B? In this form no, because the license of B specifies

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: [..] 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

So if we not met condition 2, we can not use B into C.

If we follow precisly these instructions, then C binary application should print a license like this

Copyright (c) 2016, Acme Inc.
All rights reserved.

You can use and distribuite this software only if you own a 
valid commercial license from Acme Corporation Inc.

This software uses modified parts of B software, and according its license

Copyright (c) <year>, <copyright holder>
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this
   list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
   this list of conditions and the following disclaimer in the documentation
   and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

So C license is saying that C must be distributed according the BSD-2 license, and not according a commercial license, because we are stating that the receiver of C can redistribuite it rather freely.

Maybe the first part of C license (the commercial part), is stronger than the second part based on BSD license (the permissive part). But this is not possible because if we do not respect the B license, we can not modify and redistribute it in C.

Maybe the BSD license is referring only to the original B source code, while C source code can be released under a commercial license. But what is the point saying that the B part in a binary product C can be redistributed freely, if we can not separate B from C? Without further specifications the license is referring to the entire C product, result of the modification of B source code.

Worse, if we read the BSD license it does not say in any point that we can relicense the code under other licenses. It says to copy (then propagate) the same BSD license of the B product, also to the derived C product.

More you try to comply precisly with the BSD license, and more it seems a viral license like the GPL.

What is the solution? In my opininion, after a discussion in the Haskell-ITA IRC, the solution is in interpreting the statements of the BSD license with the maximum precision.

The BSD license is composed of these parts:

1. copyright information
2. paragraph stating that some conditions must be met, i.e. the part Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
3. list of conditions
4. disclaimer of responsibility

The condition in part 3 says a precise thing

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

It is saying, in a subtle way, that you must include parts 1, 3 and 4, but not part 2. So the C license must be something like

Copyright (c) 2016, Acme Inc.
All rights reserved.

You can use and distribuite this software only if you own a 
valid commercial license from Acme Corporation Inc.

This software uses modified parts of B software, with copyrights:

Copyright (c) <year>, <copyright holder>
All rights reserved.

According B software license:

1. Redistributions of source code must retain the above copyright notice, this
   list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
   this list of conditions and the following disclaimer in the documentation
   and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

In this form the license makes sense, and it enforces only the citation of original authors, and the fact that they are not responsible for damages. Apart this aspect, the license is for sure very permissive. It is also fair from an accademic point of view, because work attribution is never lost.

Note that from a certain point of view the BSD license is "viral" like the GPL license, in the sense that also a product D based on C source code, can use C only if it mentions the original authors of B and only if D includes in the license the same obligations to cite B authors in all derived works. So you can never loose the attribution of the work of B, if B is released under the BSD license.

The same conclusions apply also in case product C is distributed as source code. In this case we apply the condition 1. instead of 2.

The strange facts are that:

• it is not true that the BSD license is easy to understand, because the exact requirements to met are very subtle, and probably they can be stated in a more explicit form from the license
• also authoritative web sites of important software companies using BSD source code in their products do not provide clear answers
• the Free Software Foundation web site confirms that the BSD license is compatible with the GPL license, but there is no a clear draft of how to comply to it

Applying a software license is like executing the instructions of a program: if you follow precisley the statements, then the license effects should be clear and unambiguous. In case of BSD the instructions were not so clear, but if we try to test and "debug" also other permissive licenses, there are worse problems.

ISC License

This is the text of the ISC license:

Copyright (c) 4-digit year, Company or Person's Name
Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

If we apply this license to a commercial product C, then C final license should say that

Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby granted, provided that the above copyright notice and this permission notice appear in all copies.

So if you receive a copy of C you can distribute it freely. It seems that ISC license is viral in the sense of the GPL, and not of the BSD license.

MIT License

The MIT license says

Copyright (c)
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

If we apply it in a precise way, then the license is saying:

• you can do whatever you want (modify, merge, publish, etc..)
• you can do whatever you want, only if you include in the final product a license saying that the receiver can do whatever he want, whenever he include this same license in his derivate products, and so on at infinitum for every derived product

So it seems a viral license like the GPL, because the same permissive rights are transferred also to the receiver of the derived work.

WTF License

WTF license says

             DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE 
                    Version 2, December 2004 

 Copyright (C) 2004 Sam Hocevar <sam@hocevar.net> 

 Everyone is permitted to copy and distribute verbatim or modified 
 copies of this license document, and changing it is allowed as long 
 as the name is changed. 

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE 
   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION 

  0. You just DO WHAT THE FUCK YOU WANT TO.

The license says that you have maximal freedom for "copying, distribution and modification" of something that is not specified. Implicitely it should be the project/software/file released under the WTF license.

The license in the beginning says also that everyone can copy, distribute verbatim or modified copies of the license document, and you can change the license only if you change the name of the license. In this case the subject of the discourse is not the project/software/file released under the WTF license, but the license itself, called "license document". "License document" for an header to put in every source file sounds a little strange, but it is acceptable.

But it is not so acceptable that in the next sentence the subject of the changes is not anymore the "license document", but the software project, or the file, but it remains unspecified.

So WTF is simple, but a little confusing if applied in a pedantic way. In any case it is for sure a liberal license.

Apache-2.0 License

Apache-2.0 license  is a long license, but it is evident that a lot of care is put in it, because it defines clearly the terms used. In the first part it can be followed precisley without problems. Then in the last parts it says

4. Redistribution. You may reproduce and distribute copies of the Work or Derivative Works thereof in any medium, with or without modifications, and in Source or Object form, provided that You meet the following conditions:

ok...

You must give any other recipients of the Work or Derivative Works a copy of this License; and

Note that it is not saying that you must apply the Apache license also to derivative works, but only that you must include a copy of this license as reference. This is sound, because if you cite in product C that you are using a product B with Apache license, then you had to include a complete copy of the license as reference. Important also because the license speaks also about patents litigations.

You must cause any modified files to carry prominent notices stating that You changed the files;

Ok clear. If you modify a source code file, you must add you as author to it in the header. It is considered best-practice also in case of the BSD license, but in this case it is stated clearly. So for every source code file (also if kept private) you have the complete list of authors.

and You must retain, in the Source form of any Derivative Works that You distribute, all copyright, patent, trademark, and attribution notices from the Source form of the Work, excluding those notices that do not pertain to any part of the Derivative Works;

Ok rather clear.

and If the Work includes a "NOTICE" text file as part of its distribution, then any Derivative Works that You distribute must include a readable copy of the attribution notices contained within such NOTICE file, excluding those notices that do not pertain to any part of the Derivative Works, in at least one of the following places: within a NOTICE text file distributed as part of the Derivative Works; within the Source form or documentation, if provided along with the Derivative Works; or, within a display generated by the Derivative Works, if and wherever such third-party notices normally appear. The contents of the NOTICE file are for informational purposes only and do not modify the License. You may add Your own attribution notices within Derivative Works that You distribute, alongside or as an addendum to the NOTICE text from the Work, provided that such additional attribution notices cannot be construed as modifying the License.

Ok you must keep the list of original authors like BSD, but also the notices they put in NOTICE file, in case there is one.

You may add Your own copyright statement to Your modifications and may provide additional or different license terms and conditions for use, reproduction, or distribution of Your modifications, or for any such Derivative Works as a whole, provided Your use, reproduction, and distribution of the Work otherwise complies with the conditions stated in this License.

Ok you can add additional license conditions to the derived work C, so C can became a commercial product. Note that:

• the Apache license is saying explicitely that you can add additional license terms and conditions to a derived product C, while MIT and BSD license are not saying explicitely this
• the Apache license is not saying that the receiver of the product C has all the rights of Apache license also on product C, so Apache license is not viral

We can follow the Apache license precisley, without bad surprises, because it uses clear and direct sentences. Also if it is a license with a long text, in practice on every source code file only a small header must be put, and the complete license is only put in the shipped LICENSE file. So there is no cost for this additional precision.

Old Conclusions (with logical errors inside)

Applying a software license is like executing the instructions of a program: if you follow precisley the statements, then the license effects should be clear and unambiguous.

In my humble opinion, if I follow the ISC and MIT license precisely, then they have a viral behavior like the GPL, so they are not permissive. Probably I'm making some mistake in their interpretation, because all the world is saying that they are very permissive. But if they are permissive, then I doubt that their text and interpretation is clear and simple, and I would be no happy to defend them in a court.

I think that the BSD-2 is a permissive license, but only interpreting the license text in a rather convoluted way. So also in case of BSD I would be no happy to defend it in a court.

 Apache 2.0 is a permissive license, and it has by far the most clear and comprehensible text, also if it is not short. So it should be used in all OSS projects needing a permissive license.

All this, obviously in my humble opinion, because I'm not a lawyer.

Elm is a Funnny Language

I used Elm (a functional programming language for writing webapps), in a moderately complex project, and I enjoyed it.

Elm has a syntax similar to Haskell, but its semantic is much simpler because it has no classes.

This simplicity is a selling point of Elm, because I see Elm more like a replacement/competitor of JavaScript and its overwhelming ecosystem of libraries, than a competitor of Haskell. Elm semantic is more elegant and predictable than JavaScript, and it has few and more integrated libraries. So the passage from JavaScript to Elm has a lot of advantages from my point of view, and very few disadvantages.

On the contrary Elm can not replace a feature-rich and complex Haskell code-base, because Haskell is based on generic and reusable abstractions like Monoid, Functor, Monad, Traversable, but Elm can not support them without the class concept. Elm sticks to clasical functional programming: no classes, no ad-hoc polymorphism, but only generic functions like map, filter and so on.

Haskell is a general-purpose, multi-paradigm programming language, and you can choose between different type of architectures: e.g. functional reactive programming (FRP), software transactional memory (STM), applicative or monadic domain specific languages (DSL).

On the contrary Elm is laser focused on single-page webapps. For this domain, it enforces a common and fixed architecture, based on a Model, updated by asynchronous Commands and Tasks. After the changes, the view function converts the Model into elements of the user-interface. The Elm platform takes care of updating the user interface in an efficient and incremental way, without recomputing it from scratch, when small parts of the Model are changed. So in an Elm application you have only readable generative code, without low level details about incremental updates.

When you study an Elm application, you know in advance its architecture. This is an advantage respect Haskell (less different programming paradigms) and JavaScript (few and more integrated libraries).

This is an example of Elm code, that converts an ActiveExplosion value of the model, into an Svg value of the user-interface. In particular to a fading circle.

drawExplosion : Model -> Float -> ActiveExplosion -> Svg Msg
drawExplosion model activationTime e =
    let opacity = Basics.max 0.0 (1.0 - (currentTime - activationTime) / (e.deactivationTime - activationTime))
    in  Svg.circle [ cx (toString e.centerX)
                   , cy (toString e.centerY)
                   , r (toString 45.0)
                   , fill (model_fromColorToExplosionGradientId model e.color)
                   , fillOpacity (toString opacity)
                   ] []

Elm functional code can be used also for generating HTML and SVG documents. This is an Elm expression generating the NetRobots logo:

Svg.svg 
  [preserveAspectRatio "xMinYMin meet"
  , viewBox "0 0 350 75"
  , width "100%"
  ,  height "100%"]
  [ g [ Svg.Attributes.style "overflow:hidden; text-anchor: middle; font-size:45; font-weight: bold; font-family: Impact"]
      [text' 
         [ x "175"
         , y "55"
         , Svg.Attributes.style "fill: white; stroke: #0f9; stroke-width: 14"]
         [Svg.text "NetRobots"]
      , text' 
          [ x "175"
          , y "55"
          , Svg.Attributes.style "fill: white; stroke: #99f; stroke-width: 8"] 
          [Svg.text "NetRobots"]
      , text' 
          [ x "175"
          , y "55"
          , Svg.Attributes.style "fill: white; stroke: black; stroke-width: 2"] 
          [Svg.text "NetRobots"]
     ]
  ]

This is the generated SVG document:

<svg preserveAspectRatio="xMinYMin meet" viewBox="0 0 350 75" width="100%" height="100%">
  <g style="overflow:hidden; text-anchor: middle; font-size:45; font-weight: bold; font-family: Impact">
    <text x="175" y="55" style="fill: white; stroke: #0f9; stroke-width: 14">NetRobots</text>
    <text x="175" y="55" style="fill: white; stroke: #99f; stroke-width: 8">NetRobots</text>
    <text x="175" y="55" style="fill: white; stroke: black; stroke-width: 2">NetRobots</text>
  </g>
</svg>

Elm expressions can be combined together, for factoring out repeated patterns, like in this case:

let netRobotsText strokeColor strokeWidth = 
      text' 
        [ x "175"
        , y "55"
        , Svg.Attributes.style ("fill: white; stroke: " ++ strokeColor ++ "; stroke-width: " ++ strokeWidth")]
        [Svg.text "NetRobots"]

in Svg.svg 
     [preserveAspectRatio "xMinYMin meet"
     , viewBox "0 0 350 75"
     , width "100%"
     ,  height "100%"]
     [ g [ Svg.Attributes.style "overflow:hidden; text-anchor: middle; font-size:45; font-weight: bold; font-family: Impact"]
         [ netRobotsText "#0f9" "14"
         , netRobotsText "#99f" "8"
         , netRobotsText "black" "2"]
     ] 

Summing up, Elm is useful only for writing single-page webapps, and it is:

• simpler and more powerful than JavaScript
• simpler but less powerful than Haskell